贪婪算法硬币更换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