完全リュック問題状態遷移方程式の解釈

完全リュック問題状態遷移方程式の解釈
ここ数日ずっとリュックの問題を見ていて、長い間見てやっと完全にリュックの問題O(VN)のアルゴリズムの原理を理解して、ここで記録して、後で忘れることを防止しますこれは私がリュックの9を見た後に総括する1種の構想です
完全バックパック問題には基本構想と改良されたO(VN)アルゴリズムがあり,この2つの状態遷移方程式は基本的にすべての関連ブログに現れる.
基本的な考え方
0−1リュックサックの問題と同様に、f[i][v]で、前のi種の物品がv容量のリュックサックを入れる最大価値状態遷移方程式を表す.

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<= v}

これは分かりやすいはずですが、0-1リュックサックの問題に基づいて得られたものです
O(VN)アルゴリズム
容量vのリュックサックにN種を入れた最大の価値をf[v]で表す
疑似コードは次のとおりです.

for v = 0 ... V do f[v] = 0
for i = 1 ... N do
	for v = c[i] ... V do
		f[v] = max{f[v], f[v-c[i]] + w[i]}

一つの考え方
このアルゴリズムは前の基本構想から最適化することができる.まず,基本構想の状態遷移方程式は以下のように最適化できる.

f[i][v]=max{f[i-1][v], f[i][v - c[i]] + w[i]}

これは,f[i][v - c[i]] + w[i] = max{f[i-1][v - c[i] - k*c[i]] + k*w[i]} | 0 <= k*c[i] <= v-c[i]これが基本構想の状態遷移方程式から得られるからである.
この式があるとO(VN)アルゴリズムが容易に得られ,空間を1次元に最適化するだけでよい.また、算出f[i][v]はi行目の値、すなわち更新された値を用いているため、内ループはc[i]からVまで遍歴し、0-1リュック問題の順序とは正反対である