今更ナップサック系DPの再勉強

Kyoto University Programming Contest 2019 B: ナップサック問題

https://atcoder.jp/contests/kupc2019/submissions/10107140

もっと早く復習するべきだったが、他にも学ぶアルゴリズムが大量にあって、今更なタイミングになってしまった。

ナップサックDPでは以下を暗記するべきかと思う。

• ナップサックDPでは品物n、重さ、価値の3要素が登場するが、y軸に品物n、x軸は制約以下の要素、DP[y][x]を残りの1要素に決め打ちして良い。難問での責任は取らない。
• ①について、ほぼ絶対に1つ前のdp2つをmaxで採用する。つまり、制約以下の要素を要素B[x]、残りの1要素を要素C[x]としたとき、dp[y][x] = max(dp[y-1][x], dp[y-1][x - 要素B[x]] + 要素C[x])とするだけ。簡単！
• 提出コードを見れば分かるが、残り1要素C[x]とDP[y][x]は同じ単位を指しているので混乱しないように注意。説明はサボる。
• ②について、採用しない場合は1つ前のdp値をそのまま引き継ぐ。

---

このように暗記すると、制約を価値にするDPも同じように解ける。

Educational DP Contest E: Knapsack 2

https://atcoder.jp/contests/dp/submissions/6890352

終わり。