7K12 blog

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

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

f:id:tkr987:20200526011654p:plain

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

  • 初期値は dp[0]=0
  • 繰り返しは rep(i, 1, Size(newItem)) rep(j, 0, n * Pow10(4) + 1)
  • 更新は if (0 <= j - newItem[i].first) dp[i][j] = max({ dp[i][j], dp[i - 1][j], dp[i - 1][j - newItem[i].first] + newItem[i].second }); など
  • 出力は rep(j, 0, W + 1) ans = max(ans, dp.back()[j]);

f:id:tkr987:20200526013743p:plain

ナップサックDPの定石としてDPの行を商品、DPの列を 10^6程度の要素にする、と暗記する。芋づる式のデータ構造にunion-findを使うのも定石なので暗記する。各要素を集合にしていくと商品インデックスに空白が出来るが、値が0ならDP更新されないので気にせずナップサックの処理を書いて良い。ただし、値0では前のDPを引き継ぐことを忘れずに書く。商品インデックスの先頭にダミーを入れておくと更にDPが書きやすくなる。また、列のDPサイズが n \times Wmax + 1になることに注意する。