貨幣交換の欲張りアルゴリズムC++

Question

したがって、値Nと任意の金額を取るコイン変更アルゴリズムを作成しています.1を持たない場合は、自動的に1を含める必要があります。私はすでにこれをしましたが、欠陥があります。私は2つのマトリックスを持っています。私はそれらの1つを使用する必要があります。 S [i]行列を書き直しても、配列の大きさを増やすことは可能ですか？また、最小金額まで、最大金額と2番目に高い金額を見つける方法はありますか？私はそれを簡単にするために最高から最低に並べ替えるべきですか、それを次々に探し出す簡単な方法がありますか？

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