ツバサの備忘録

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

2019-01-31

Educational DP Contest / DP まとめコンテスト E - Knapsack 2

解法

$dp[i][j] = i$ 番目までの品物を利用して合計が価値が $j$ となるような組み合わせの中での合計重量の最小値
とします。
$dp[i][j] = min(dp[i-1][j],dp[i-1][j-v_{i}]+w_{i})$
となります。あとは、 $dp[0][j]$ を $\infty$ で、 $dp[i][0]$ を0で初期化し、このDPを解くことで、 $dp[N][j] \neq \infty$ となる $j$ の最大値を求めれば、これが答えになります。