DPまとめコンテスト/D - Knapsack 1 - 競技プログラミング用 知識集積所【7/10更新】

---

問題

DP-D

必要知識

ABCのB以下レベルの内容は省略

• 動的計画法

考え方

最も標準的な形のナップサック問題。
ただし、個数や値の制約によりその解き方は大きく変わる。

• N<20くらいであれば、bit全探索（未作成）
• N<40くらいであれば、半分全列挙（未作成）
• N*W<1億くらいであれば、動的計画法
• N^2*v_max<1億くらいであれば、双対性（未作成）を利用した動的計画法

あたりがメジャーなところか。

今回はNが最大100、Wが最大10万、v_maxが10億であるため、N*W<1億の場合の解き方を実行する。
この場合は、動的計画法のところに紹介した部分和問題の解き方を応用することができる。

例えば、

品物1：重さ1 価値2
品物2：重さ3 価値4
品物3：重さ4 価値3

で重さ上限5の場合を考える。

まず、価値を無視してどんな重さ合計を作ることができるか？を考える。
これ自体は部分和問題そのものなので、以下のような表を作ることになる。

	重さ合計
品物	0	1	2	3	4	5
なし	o	x	x	x	x	x
+品物1	o	o	x	x	x	x
+品物2	o	o	x	o	o	x
+品物3	o	o	x	o	o	o

青色は、「{1}で1を作れるか？」は{}で0を作れるのでo。
黄色は、「{1,3,4}で4を作れるか？」は{1,3}で0も4も作れるのでo。

この各データのo部分に、代わりに「その場合の最大価値は？」を入れていく。

	重さ合計
品物	0	1	2	3	4	5
なし	0	x	x	x	x	x
+品物1	0	2	x	x	x	x
+品物2	0	2	x	4	6	x
+品物3	0	2	x	4	6	5

青色：「{1}で1を作れるか？」は{}で0を作れるので最大価値は0+2=2。
黄色：「{1,3,4}で4を作れるか？」は{1,3}で0も4も作れるので最大価値は0+3=3と6の大きい方で6。

そして、最終的に最下段の中での最大数を答えればよい。
つまり、この場合の答えは6。

……という方法でも解けるのだが、この方法は

• うっかり右下を答えるミスをしがち
• 可能か不可能か判断→可能なら値を計算という二段階処理が面倒

という欠点がある。
そこで、DPとして持つ値を「合計重さがiである」ではなく「合計重さがi以下である」と変更して考える。
そうすると、表が以下のようになる。

	重さ合計
品物	0	1	2	3	4	5
なし	0	0	0	0	0	0
+品物1	0	2	2	2	2	2
+品物2	0	2	2	4	6	6
+品物3	0	2	2	4	6	6

青色：「{1}で1以下を作れるか？」は最大価値は0+2=2と0の大きい方で2。
黄色：「{1,3,4}で4以下を作れるか？」は最大価値は0+3=3と6の大きい方で6。

つまり、作れるかどうかのチェックが不要になり、しかも解答は右下を提出するだけでよくなる。
コードの変更点は、最上段の初期化を全部0で初期化するように変更するだけでよい。
こちらの実装が簡単なので。可能ならこちらで書きたい。

解答例

解答例

注意点

別解