硬幣找零問題C++

我有寫一個動態的算法來解決硬幣找零問題，我有一個問題是這樣的：硬幣找零問題C++

ARR [值] - 一個全球性的陣列充滿0，lenght價值我想解決;

a [n] - 具有硬幣值的數組;

void dynamic(int n, int *a, int value) { 
arr[0]=0; 
for(int i=1;i<value;i++){; 
    for(int j=0;j<n;j++){ 
     if(i==arr[j]) arr[i]=1; 
     else{ 
      arr[i] = arr[i-1] + 1;   
     } 
    } 
}}

我知道我是怎麼想這樣做，但我不知道如何實現它。

例如：
比方說，我有硬幣1 4 10 15 40和值37解決。我正在填寫這樣的數字：
如果硬幣值= i我arr [i] = 1;對於下一個元素，只要我低於下一個硬幣，我把之前的值+ 1，arr [i-1] +1。
所以這應該填充arr [i]像這樣1 = 1,2 = 2,3 = 3，4 = 1，5 = 2等等，但我錯過了一些東西，不知道如何以正確的方式填充它。

有人可以按照我想要的方式做到這一點嗎？我一直在試圖找出它，但沒有發現是正確的。我甚至使用遞歸來編寫整個算法，但它太慢了，所以我需要重新編寫一遍。

來源

2011-03-16 Paul

聽起來像家庭作業。你正在處理揹包問題。對於任何「大型」輸入，它總是會很慢：http://en.wikipedia.org/wiki/Knapsack_Problem – 2011-03-16 17:06:36

這不是一個家庭作業，如果它是我不會再按我想要的方式寫入它。 – Paul 2011-03-16 17:08:21

相關SO問題：http://stackoverflow.com/questions/1518330/coin-change-problem-with-infinite-number-of-coins-of-each-denomination – AJG85 2011-03-16 17:48:58

你可能想：

memset(arr,0,sizeof(arr)); 
arr[0]=1; 
for(int i=0;i<n;++i) 
    for(int j=a[i];j<value;++j) 
     arr[j]+=arr[j-a[i]];

這應該是如果我理解你的權利，基本上這是一個巧妙的方法來實現遞歸正確...

f[i,j]=f[i-1,j]+f[i-1,j-a[i]];

顯然，這需要時間O(n Value) 。

來源

2013-02-16 06:13:19 phoeagon

硬幣找零問題C++

回答

相關問題