ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

こちらと全く同じです。

$dp[i][j] = i$ 番目までの品物を使って、重さの合計が $j$ となるような組み合わせの中での価値の最大値
とすると、
$dp[i][j] = max(dp[i-1][j],dp[i-1][j-w_{i}] + v_{i})$
となります。
答えは $dp[N][j]$ の最大値です。