7K12 blog

猫でも分かるアルゴリズム解説

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

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

f:id:tkr987:20200216003032p:plain

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

 

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

f:id:tkr987:20200216004244p:plain

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

  • ナップサックDPでは品物n、重さ、価値の3要素が登場するが、y軸に品物n、x軸は制約 10^{5}以下の要素、DP[y][x]を残りの1要素に決め打ちして良い。難問での責任は取らない。
  • ①について、ほぼ絶対に1つ前のdp2つをmaxで採用する。つまり、制約 10^{5}以下の要素要素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

f:id:tkr987:20200216004507p:plain

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

終わり。