個数制限なしナップサック問題

問題例

N個の品物があります。 品物には1,2,…,Nと番号が振られています。 各i(1≤i≤N) について、品物iの重さはwiで、価値はviです。太郎君は、N個の品物のうちいくつか(複数可) を選び、ナップサックに入れて持ち帰ることにしました。ナップサックの容量はWであり、持ち帰る品物の重さの総和はW以下でなければなりません。太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

引用: https://atcoder.jp/contests/dp/tasks/dp_d(一部編集)

考え方

dp[i][j](i番目までの品物から重さの合計がj以下になるように選んだ時の価値の最大値)とおいて、k個まで選べるようにしてmax(dp[i][j - k * w[i]] + k * v[i], dp[i + 1][j])とすると3重ループになってしまう。

しかしよく考えると、k(k >= 1)のとき、何回も同じ計算をしていることがわかる。なぜなら、dp[i + 1][j]の計算においてk個選ぶ場合は、dp[i + 1][j - w[i]]の計算においてk - 1個選んでいるのと同じだからである。

したがって、次のような式変形ができる。(蟻本p59より引用)

dp[i + 1][j]

= max{dp[i][j - k * w[i]] + k * v[i] | 0 <= k} //0 ~ k個順番に選んで計算している

= max(dp[i][j], max{dp[i][j - k * w[i]] + k * v[i] | 1 <= k})

= max(dp[i][j], max{dp[i][(j - w[i]) - k * w[i]] + k * v[i] | 0 <= k} + v[i]) dp[i + 1][j - w[i]]のときk - 1個選んでいる

= max(dp[i][j], dp[i + 1][j - w[i]] + v[i])

(総括)dp[i + 1][j]の選び方の考え方

個数制限あり...max(dp[i][j], まだi+1個目の品物はえらんでいないはずだから、i個目までの中から重量j - w[i]以内になるようにしたときの価値の最大値 + 今回の品物の最大値)
個数制限なし...max(dp[i][j], (複数選べるため)i+1個目がすでに選ばれている可能性があるので"i + 1個目"までの中から重量j - w[i]以内になるようにしたときの価値の最大値+ 今回の品物の最大値)