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

---

問題

DP-E

必要知識

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

• 動的計画法
• 双対性（未作成）

考え方

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

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

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

今回はNが最大100、Wが最大10億、v_maxが1000であるため、N^2*v_max<1億の場合の解き方を実行する。
この場合は、双対性（未作成）を利用した動的計画法で解くことになる。

例えば、前問と同じ

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

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

前問と同じように動的計画法の表を作る（重さ上限が5なのは一旦見ない）と、最下段は以下のようになる。

	重さ合計
品物	0	1	2	3	4	5	6	7	8
全部	0	2	2	4	6	6	6	7	9

これは、もちろん

• Wが0以下では、Vは最大で0
• Wが1以下では、Vは最大で2
• Wが2以下では、Vは最大で2
• Wが3以下では、Vは最大で4
• Wが4以下では、Vは最大で6
• Wが5以下では、Vは最大で6
• Wが6以下では、Vは最大で6
• Wが7以下では、Vは最大で7
• Wが8以下では、Vは最大で9

という意味である。

しかし、これは見方を変えると

• Vが0以上では、Wは最小で0
• Vが1以上では、Wは最小で1
• Vが2以上では、Wは最小で1
• Vが3以上では、Wは最小で3
• Vが4以上では、Wは最小で3
• Vが5以上では、Wは最小で4
• Vが6以上では、Wは最小で4
• Vが7以上では、Wは最小で7
• Vが8以上では、Wは最小で8
• Vが9以上では、Wは最小で8

ということでもある。

ということは、

	価値合計
品物	0	1	2	3	4	5	6	7	8	9
全部	0	1	1	3	3	4	4	7	8	8

というものをDPの表の最下段に作れれば、「Wの最小値が5以下になるにはVの上限は6以下」という情報から6と解答することができる。
一見ただ遠回りなことをしているだけのようだが、w[i]が大きいがv[i]が小さい場合はこちらの方が表が小さくなるメリットがある。

ということで、双対性（未作成）を利用する場合はこのような表を作ることになる。

	価値合計
品物	0	1	2	3	4	5	6	7	8	9
+なし	0	x	x	x	x	x	x	x	x	x
+品物1	0	1	1	x	x	x	x	x	x	x
+品物2	0	1	1	3	3	4	4	x	x	x
+品物3	0	1	1	3	3	4	4	7	8	8

青色：品物1を使う場合、0+1=1。品物1を使わない場合、x。最小値は1。
赤色：品物2を使う場合、0+3=3。品物2を使わない場合、1。最小値は1。
黄色：品物3を使う場合、3+4=7。品物2を使わない場合、4。最小値は4。
（赤色のところで、使わない場合の「品物1までで価値-3以上である」は重さ0で可能であることに注意）

最後は、最下段の中で5以下の値が入っている最後の値を答えればよい。
これは、愚直に右から全探索（未作成）をしてもいいし、二分探索（未作成）を用いてもよい。

解答例

解答例

注意点

別解