詳盡搜索：用於更改的最小硬幣數量。在使用遞歸時保留解決方案陣列

Question

問題在於儘量減少提供確切更改所需的硬幣數量。總是會有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; 
} 

Answer 1

您仍然可以做到這一點使用數組，但我會改變程序的結構，使其一點點清潔遞歸。

我將不得不僞造這個給你，因爲我根本不使用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++語法的你，但它不應該是太難翻譯我做了什麼在這裏進入你想要做的事情。

如果您有任何問題，請告知我