2

問題は、正確な釣り銭を与えるために必要なコインの量を最小限に抑えることにあります。常に 1 のコインが利用できるため、問題には常に解決策があります。

40 セントのソリューションを含むいくつかのサンプル コイン セット:

コイン セット = {1, 5, 10, 20, 25}、解 = {0, 0, 0, 2, 0}

コイン セット = {1, 5, 10, 20}、解 = {0, 0, 0, 2}

実装は正しい分を返します。コインの数ですが、正しいソリューション配列を維持するのに問題があります。

int change(int amount, int n, const int* coins, int* solution) {
    if(amount > 0) {
        int numCoinsMin = numeric_limits<int>::max();
        int numCoins;
        int imin;
        for(int i = 0; i != n; ++i) {
            if(amount >= coins[i]) {
                numCoins =  change(amount - coins[i], n, coins, solution) + 1;
                if(numCoins < numCoinsMin) {
                    numCoinsMin = numCoins;
                    imin = i;
                }   
            }   
        }   
        solution[imin] += 1;
        return numCoinsMin;
    }   
    return 0;
}

サンプルラン:

int main() {
    const int n = 4;
    int coins[n] = {1, 5, 10, 20, 25};
    int solution[n] = {0, 0, 0, 0, 0};
    int amount = 40;

    int min = change(amount, n, coins, solution);
    cout << "Min: " << min << endl;
    print(coins, coins+n); // 1, 5, 10, 20
    print(solution, solution+n); // 231479, 20857, 4296, 199
    return 0;
}
4

1 に答える 1

0

配列を使用してこれを行うこともできますが、プログラムの構造を変更して、再帰するのが少しきれいになるようにします。

私は C++ をほとんど使用しないため、これを疑似コード化する必要がありますが、おそらくまとめることはできます。これは剰余除算 (C# では %、C++ で同じ場合は不明、調べることができます) を使用し、除算の残りのみを返します。また、ほとんどのプログラミング言語の通常の除算 (/) では、整数の答えが返され、余りは無視されます。

//declare a function that takes in your change amount and the length of your coins array
int changeCounter(int amount, int coins.length)
      int index = coins.length-1;

      //check to see if we're done... again dunno what 'or' is in C++, I put ||

      if (amount <= 0 || index < 0)
         **return** your results array or whatever you want to do here

      //sees how many of the biggest coin there are and puts that number in the results
      if amount > coins[index]
      {
        result[index]= (amount / coins[index])
        //now recurse with the left over coins and drop to the next biggest coin
        changeCounter((amount % coins[index]), index-1)
      }

      //if the amount isnt greater than the coin size then there obviously arent any of that size, so just drop coin sizes and recurse again
      else
         changeCounter(amount,index-1)

これにより、正しい方向に進むことができます。私はあなたのためにコメントしようとしました。申し訳ありませんが、あなたのために完璧な C++ 構文に入れることはできませんが、私がここで行ったことをあなたが試みていることに翻訳するのはそれほど難しいことではありません。する。

ご不明な点がございましたら、お知らせください

于 2012-11-02T16:53:37.657 に答える