コイン振替のための動的プログラミング

Question

コインシステムC = {c1、c2、... ck}において、所与の金額xは、各コインciが所定の重量wiを有するように変更されるべきである。可能な変更の総重量を計算したいと考えています。同じコインが異なる順序で含まれていると、2つの変更が異なります。

上記の問題に対してどのように動的プログラミング再帰を与えることができますか？最小コイン変更問題（すなわち、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); 
}