[AtCoder] Educational DP Contest D – Knapsack 1

問題

方針

いわゆるナップザック問題ですね。

\( d(i, j) \) を品物 \( i \) まで調べたとき、重さの総和が \( j \) であるときの価値の総和の最大値とします。初期値は、\( d(0, 0) = 0 \) で、それ以外は \( d(i, j) = -1 \) とします。遷移は次のようになります。

  • \( d(i, j) \neq -1\) のとき

品物\( i \) を持ち帰ることを考えると、

\[d(i +1, j + w[i]) = \max(d(i + 1, j + w[i]), d(i, j) + v[i])\]

となり、品物を持ち帰らないとすると、

\[d(i +1, j) = \max(d(i + 1, j), d(i, j))\]

となります。よって、答えは、\(d(N, \cdot)\) の最大値となります。

コード