コインの交換のための空間最適化ソリューション

Question

値Nを与えた場合、Nセントに変更したい場合、S = {S1、S2、..、Sm}値のコインのそれぞれを無限に供給すると、私たちは変更を加えることができますか？コインの順序は関係ありません。例えば、N = 4およびS = {1,2,3}の場合、{1,1,1,1}、{1,1,2}、{2,2}の4つの解が存在する。 、{1,3}。出力は4でなければなりません。N = 10、S = {2、5、3、6}の場合、{2,2,2,2,2}、{2,2,3,3}、 {2,2,6}、{2,3,5}、{5,5}である。出力は5になるはずです。

私は3つのアプローチを見つけましたHERE。しかし、空間的に最適化された動的プログラミングアプローチを理解することはできません。ここでは、1次元の配列表[]のみが使用されています。

int count(int S[], int m, int n) 
{ 
    // table[i] will be storing the number of solutions for 
    // value i. We need n+1 rows as the table is consturcted 
    // in bottom up manner using the base case (n = 0) 
    int table[n+1]; 

    // Initialize all table values as 0 
    memset(table, 0, sizeof(table)); 

    // Base case (If given value is 0) 
    table[0] = 1; 

    // Pick all coins one by one and update the table[] values 
    // after the index greater than or equal to the value of the 
    // picked coin 
    for(int i=0; i<m; i++) 
     for(int j=S[i]; j<=n; j++) 
      table[j] += table[j-S[i]]; 

    return table[n]; 
} 

Answer 1

まずなお、表[i]はN = I硬貨釣銭用のいくつかの方法です。

与えられたコイン（S []）のセットごとに、与えられたアルゴリズムがこの配列（テーブル[]）を埋めます。 最初に、テーブル[]のすべての値は0に初期化され、テーブル[0]は0に設定されます（これは基本ケースN = 0です）。

各コインは、以下のようにテーブル[]に値を合計します。これは理解しやすい

1. テーブル[X] =テーブル[X] + 1

   - 以下の値Xの硬貨について

   は、テーブルの更新[]です。具体的には、解{X}を追加します。すべてのY> X

   テーブルの

2. [Y]テーブル[Y] +テーブル= [Y-X]

   これは理解するのが難しいです。例X = 3をとり、Y = 4の場合を考える。

   4 = 3 + 1すなわち3は3と1を組み合わせて得られる。定義の通り、1を得る方法の数は表[1]である。テーブル[4]には多くの方法が追加されています。なぜ上記の式はテーブル[Y-X]を使用しているのですか？あなたのアルゴリズムで

次の行が（2つの工程以上）同じ - を表すアルゴリズムの終わりに

table[j] += table[j-S[i]]; 

、テーブル[n]はnの溶液を含有します。

Answer 2

この方法でアルゴリズムを理解してみてください。

table[i][j]は、jの値を変更するために最初のiコインのタイプを使用することを意味します。その後：jコインを作るとき

table[i][j] = table[i-1][j] + table[i][j-S[i]]

は明らかに、あなたは、2つの選択肢があります。 i番目のコインを使用していないか、i番目のコインを使用していません。 i番目のコインを使用しない場合、解の数はtable[i-1][j]です。 i番目のコインを使用する場合、解答番号はtable[i][j-S[i]]です。これは、最初のiコインを使用してjS [i]値を構成することを意味します。したがって、合計は両方の和です。table[i-1][j] + table[i][j-S[i]]

コードでは、 forループが表示されます。外側のループはiを反復し、内側のループはjを反復する。 +=ステートメントは上記の式に基づいてtable[i][j]を計算します。あなたのコード内

EDIT

table[j]実際に私は上記話しているtable[i][j]あるとiはあなたのループ内の値です。ループtable[N]がtable[M][N]を意味し、最初のMの硬貨を使用して表しており、すべてコインであり、Nの値になります。

Iはコードに基づいて詳細を提供する：

for(int i=0; i<m; i++) 
     for(int j=S[i]; j<=n; j++) 
      table[j] += table[j-S[i]]; 

場合i = 0、値jための変更を加える第1コインを用いtable[j]手段。例えば、table[2]は今2.そうするために変更を加えるためにcoins {1}を使用することを意味した：i = 0 table[1] ~ table[4]は現在の値1、2のために変更を加えるためにcoin {1}を使用することを意味する場合

table[1] = table[1] + table[1 - S[0]] = table[1] + table[0] = 1 + 0= 1 
table[2] = table[2] + table[2 - S[0]] = table[2] + table[1] = 0 + 1= 1 
table[3] = 1 
table[4] = 1 

はその後、我々は結果を得ました、 3,4、別々に。 I = 1、table[j]値jの変更を行うことcoin {1, 2}を使用することを意味

。

table[2] = table[2] + table[2 - S[1]] = table[2] + table[0] = 1 + 1= 2 
table[3] = table[3] + table[3 - S[1]] = 1 + 1 = 2 
table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3 

以下のプロセスは同じです。

は最後に、我々はtable[4]ときi = 1アウトを取り、それを分析：

table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3 

ここtable[4]左側には、私たちが計算されている値であり、実際にそれがtable[i=1][4]です。右側のtable[4]は前の値を表し、この場合はtable[i=0][4]です。それは拡大できます

は

table[i=1][4] = table[i=0][4] + table[i=1][4 - S[1]] 

式は正確である

table[i][j] = table[i-1][j] + table[i][j-S[i]] 

EDITフォローアップの質問あなたが本当に新しいと同じ問題を解決しようとすると、この質問を理解して考える場合

制約。すべてのコインを一度しか使用できない場合はどうなりますか？例えば、N = 4、S = {1,2,3}、1つの解{1,3}しかないので、出力は1でなければならない。そして、N = 10およびS = {2、5、3、6}依然として1つの解{2、3、5}と出力は1です。

ヒント：元のコードの1行の変更だけで十分です。

回答：http://ideone.com/t1JnEz