用於硬幣變化的動態編程

Question

在硬幣系統C = {c1，c2，... ck}中應該改變給定量x，使得每個硬幣ci具有給定的權重wi。我們想計算可能的變化的總重量。如果它們按不同順序包含相同的硬幣，則兩個更改會有所不同。

如何爲上述問題提供動態編程遞歸？我知道最小硬幣變化問題的遞歸（即，對於x> 0，C（x）= min {C（x-c）+1}）。但是我的困惑是可能變化的總重量。謝謝。

Answer 1

看起來像幼稚的方法「在數組中存儲答案」的作品。我們C [i]代表硬幣值，W [i]代表硬幣重量，N代表硬幣數量。

遞歸部分看起來是這樣的：

long sum = 0; 
for (int i = 0; i < N; ++i) 
    if (C[i] <= x) 
     sum += W[i] + total_change_weight(x-C[i]); 

示例程序沒有輸入，輸出和C/W初始化如下：

#define N 10 
#define MAX_VALUE 101 

long C[N]; 
long W[N]; 
long totals[MAX_VALUE]; 

long total_change_weight(long x) 
{ 
    if (x == 0) 
     return 0; 
    if (totals[x] >= 0) 
     return totals[x]; 

    long sum = 0; 
    for (int i = 0; i < N; ++i) 
     if (C[i] <= x) 
      sum += W[i] + total_change_weight(x-C[i]); 
    totals[x] = sum; 

    return sum; 
} 

void main() 
{ 
    long value = 100; 
    //initialize C 
    ... 
    //initialize W 
    ... 
    //initialize totals 
    for (long i = 0; i < MAX_VALUE; ++i) 
     totals[i] = -1; 
    long result = total_change_weight(value); 
}