Dynamic Programming for coin change

Question

A given amount x should be changed in a coin system C = {c1, c2, … ck} such that each coin ci has a given weight wi. We would like to calculate the total weight of the possible changes. Two changes are different if they contain the same coins in different order.

How can we give a dynamic programming recursion for the above problem? I know the recursion for minimum coin change problem (i.e. C(x)=min{C(x-c)+1 for x>0}). But my confusion is the total weight of the possible changes.Thanks.

Answer 1

Looks like naive approach "store answer in the array" works. Let's C[i] represents coin value and W[i] represents coin weight, N is number of coins.

Recursion part looks like this:

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

sample program without input, output and C/W initialization follows:

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