AOJ 0042 （A Thief : 泥棒）

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0042

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0042

【解説】

いわゆる0-1ナップザック問題。

動的計画法にて解いていけばよい。漸化式や解説については、リンク先のwikipediaを参照。

dpテーブル"dp[w]"を用意し、添え字は風呂敷に入っている品物の重さとしている。これを、各品物の数の分だけ操作していく。dpテーブルに入れる値は、品物iの価値を\(v_i\)、重さを\(w_i\)とすると、要素jについて、 $$ dp[j] = \max (dp[j], dp[j - w_i] + v_i)　(j - w_i ≧ 0) $$ となる。すなわち、風呂敷にその品物を入れられるだけの重さに余裕があれば、入れる前の価値に品物の価値を加えた値を求め、その値がその重さにおける価値を上回っていれば、値を更新する、ということになる。これを、配列の末尾から先頭に向かって処理していけばよい。

最後に全ての品物に対して処理した結果の配列の最大値をとれば、それが解となる。

配列を操作する場合に昇順で辿ってしまうと、同じ品物を複数入れてしまうことに注意する。

【コード】