『ナップサック問題 個数制限なし 自分用メモ』

i番目の物の重さがw(i) 価値がv(i)とする。 i番目までで重さjまででの最大になるように選んだ時の合計価値をdp[i][j]とする。 dp[i+1][j]はi+1番目をいくつか使った時と全く使わない時のうちの最大値なのでkを１以上でj-k*wが0以上を満たす自然数として dp[i+1][j]=max( dp[i][j], dp[i][j-k*w(i+1)]+k*v(i+1) ) ここで実は dp[i+1][j-w(i+1)]=max( dp[i][j-w(i+1)] , dp[i][j-w(i+1)-q*w(i+1)]+q*v(i+1) ) である。ここで右辺に既視感があることに気づく。（dp[i+1][j-w(i+1)]は第一式の右辺の dp[i][j-k*w(i+1)]+k*v(i+1)よりv(i+1)小さいのと同じじゃん） つまり第一式のmax( dp[i][j-k*w(i+1