ダイナミックプランニング(1)-01リュック【テンプレート】

問題の説明
N個の品物とV容量のリュックサックがあります.i番目のアイテムを入れるのにかかるスペースはC[i]で、得られる価値はW[i]です.リュックサックにどのアイテムを入れるかを解くと、価値の合計が最大になります.
 
基本的な考え方
それぞれの品物は1つしかなく、置くか置かないかを選ぶことができます.サブ問題で状態を定義する:すなわち、F[i,v]は、前のiつの物品がvの容量のリュックサックを入れていることを示す.
最大の価値を得る.その状態遷移方程式は,F[i,v]=max{F[i-1,v],F[i-1,v-C[i]+W[i]}である.
 
「この方程式は、前のi個の物品を容量vのリュックサックに入れることを表す」というサブ問題は、
第iの物品の策略(置くか置かないか)は、前のi-1の物品としか相容れないように変換することができる.
関連する問題.i番目のアイテムを置かないと、問題は「前のi-1アイテムを入れる容量」に変換されます.
vのリュックサックの中で、価値はF[i-1,v];i番目の品物を置くと、問題は
「前のi-1アイテムは残りの容量v-C[i]のリュックサックに入れます」というときに得られる最大の価値
F[i-1,v-Ci]に加えてi番目のアイテムを入れることで得られる価値W[i]である.
 
2 D 01リュックサック

for(int i = 1; i <= n; i++)
	for(j = C[i]; j <= v; j++)
		dp[i][j] = max(dp[i-1][j], dp[i-1][j-C[i]] + W[i]);
	//  i      		j     V
	//C[i]       		W[i]      

スペース最適化後の1 D 01リュックサック

for(int i = 0; i < n - 1; i++)
	for(int j = v; j >= C[i]; j--)
		dp[j] = max(dp[j], dp[j-C[i]] + W[i]);
	//  i      		j     V
	//C[i]       		W[i]      

に注意
リュックサックを適切に満タンにすることが要求される場合、初期化時にF[0]を除いて0となり、その他のF[1~V]は-∞とする、
これにより,最終的に得られるF[V]がリュックサックを適切に満たす最適解であることが保証される.バックを満タンにしなければならないという要求ではなく、できるだけ価格が大きいことを望んでいる場合は、初期化時に
F[0~V]は全て0とする.
これは初期化されたF配列が事実上リュックサックに入れるものがない場合の合法状であるためである.
状態.リュックがぴったり詰まっていれば、このとき容量0のリュックだけは何も入れなくてもいいです
また、価値が0の場合は「ちょうど満タン」となり、他の容量のリュックサックは合法的な解がなく、
未定義の状態は、-∞に割り当てられるはずです.リュックサックがいっぱいにならなければならないわけではない場合は、どんな容量でも
量のリュックはすべて1つの合法的な解“何も詰めません”があって、この解の価値は0で、だから初期の時状
状態の値もすべて0になります.