硬币兑换的动态规划

Question

在硬币系统C={c1，c2，…ck}中，应改变给定的数量x，以使每个硬币ci具有给定的重量wi。我们想计算可能变化的总重量。两种变化是不同的，如果他们包含在不同的顺序相同的硬币。

如何给出上述问题的动态规划递归？我知道最小硬币兑换问题的递归（即C（x）=min{C（x-C）1 for x

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);
}