algorithm - Dynamic Programming for coin change -

a given amount x should changed in coin system c = {c1, c2, … ck} such each coin ci has given weight wi. calculate total weight of possible changes. 2 changes different if contain same coins in different order.

how can give dynamic programming recursion above problem? know recursion minimum coin change problem (i.e. c(x)=min{c(x-c)+1 x>0}). confusion total weight of possible changes.thanks.

looks naive approach "store answer in array" works. let's c[i] represents coin value , w[i] represents coin weight, n number of coins.

recursion part looks this:

long sum = 0; (int = 0; < n; ++i)     if (c[i] <= x)         sum += w[i] + total_change_weight(x-c[i]); 

sample program without input, output , 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;     (int = 0; < 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     (long = 0; < max_value; ++i)         totals[i] = -1;     long result = total_change_weight(value); }