動的計画法part4(個数制限なしナップサック問題)

重さと価値がそれぞれWi,Viであるようなn種類の品物がある。
これらの品物から重さの総和がWを超えないように選んだときの、
価値の総和の最大を求めろ。
ただし、同じ種類の品物を使ってよい。

i番目までの品物から重さの総和がj以下となるように選んだときの、
価値の総和の最大値とします。

\[ dp[0][j] = 0 \]
\[ dp[i+1][j] = max(dp[i][j-k*w[i]]-k*v[i]|0<=k \]

残りjだけ入るとき、今までjだけ入ってたものから、k*w[i]分だけ抜いたときに
代わりに品物iをkだけ使った場合のコストが最大

▶︎３重ループになり計算量が増える。

よって右辺を改良する

\[ max{dp[i][j-k*w[i]]+k*v[i] | 0 <= k} \]
\[= max(dp[i][j], max{dp[i][j-k*w[i]]+k*v[i]|1<=k}) \]
(dp[i][j]はkが0個のときと等しいため)

\[ = max(dp[i][j], max{dp[i][(j-w[i])-k*w[i] + k*v[i] | 0<= k} + v[i]) \]
(再び1個分別に可算する形にする)

\[ = max(dp[i][j], dp[i+1][j-w[i]]+v[i]) \]
(同じ品物を入れる場合、一つ入れる一個手前と、前のときを比較すれば済む)

よってkに対するループがなくなる。