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