貪婪算法硬幣更換C++

Question

所以，我創建了一個硬幣更改算法，採用值N和任何數量的面額，如果它沒有1，我必須自動包括1。我已經這樣做了，但現在有一個缺陷，我有2個矩陣，我需要使用其中的1個。是否有可能重寫S [i]矩陣，並且仍然增加數組的大小......另外，我怎樣才能找到最大面額和第二高和sooo直到最小？我應該把它從高到低排列，以便讓它變得更容易，或者有更簡單的方法來一個接一個地尋找它們嗎？

int main() 
{ 
    int N,coin; 
    bool hasOne; 
    cout << "Enter the value N to produce: " << endl; 
    cin >> N; 
    cout << "Enter number of different coins: " << endl; 
    cin >> coin; 

    int *S = new int[coin]; 

    cout << "Enter the denominations to use with a space after it" << endl; 
    cout << "(1 will be added if necessary): " << endl; 
    for(int i = 0; i < coin; i++) 
    { 
     cin >> S[i]; 
     if(S[i] == 1) 
     { 
      hasOne = true; 
     } 
     cout << S[i] << " "; 
    } 
    cout << endl; 
    if(!hasOne) 
    { 
     int *newS = new int[coin]; 
     for(int i = 0; i < coin; i++) 
     { 
      newS[i] = S[i]; 
      newS[coin-1] = 1; 
      cout << newS[i] << " "; 
     } 
     cout << endl; 
     cout << "1 has been included" << endl; 
    } 

    //system("PAUSE"); 
    return 0; 
} 

Answer 1

你可以用std :: vector實現它，那麼你只需要使用push_back。

std::sort可用於按降序排列面值，然後只是檢查最後一個是否爲1，如果缺失則添加它。 （這段代碼中缺少很多錯誤檢查，例如，您應該檢查沒有面值> = 0，因爲您使用的是有符號整數）。

#include <iostream> // for std::cout/std::cin 
#include <vector>  // for std::vector 
#include <algorithm> // for std::sort 

int main() 
{ 
    std::cout << "Enter the value N to produce:\n"; 
    int N; 
    std::cin >> N; 

    std::cout << "Enter the number of different denominations:\n"; 
    size_t denomCount; 
    std::cin >> denomCount; 

    std::vector<int> denominations(denomCount); 
    for (size_t i = 0; i < denomCount; ++i) { 
     std::cout << "Enter denomination #" << (i + 1) << ":\n"; 
     std::cin >> denominations[i]; 
    } 

    // sort into descending order. 
    std::sort(denominations.begin(), denominations.end(), 
     [](int lhs, int rhs) { return lhs > rhs; }); 

    // if the lowest denom isn't 1... add 1. 
    if (denominations.back() != 1) 
     denominations.push_back(1); 

    for (int coin: denominations) { 
     int numCoins = N/coin; 
     N %= coin; 
     if (numCoins > 0) 
      std::cout << numCoins << " x " << coin << '\n'; 
    } 

    return 0; 
} 

現場演示：http://ideone.com/h2SIHs