7K12 blog

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

DPL_1_B 0-1 Knapsack Problem

f:id:tkr987:20200713205208p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4516218

  • 初期値 dp[0][w] = 0;
  • 繰り返しは rep(i, 1, Size(item)) rep(j, 0, W + 1)
  • 更新は dp[i][j] = max({ dp[i][j], dp[i - 1][j], dp[i - 1][j - item[i].second] + item[i].first });
  • 出力は dp.back().back()

f:id:tkr987:20200713210629p:plain

最初のうちはV1でDP表が埋まるが、下の行にいくほど他の値にmaxで更新されていく。更新できないとき「前のDP値を引き継ぐ」ことを忘れないように注意する。アイテムの先頭にダミーを入れておくと実装が楽になる。