DPメモ(ナップサック問題)


また別の問題でひっかかったり、この考え方では間違うと思ったら、随時修正していきます。

0-1ナップサック問題を定式化すると次のようになる。

とはいえ、バリエーションは豊富なので、上と同じような式でない問題も多数ある。
Σvxがでてきたら、ナップサック問題を念頭においておこう。
ちなみに、DP以外の解法のものも、ここで取り扱う。

■問題の目的の違い
  (A1)最大値・最小値を求める(max(Σvx) 主にナップサック問題など)
  (A2)数え上げる(Σvx=Kとなるパターン数を数える。部分和問題かな?)
  (A3)判定する(Σvx=Kとなるかどうかを判定する。部分和問題)

(A1)はmaxやmin、(A2)のときは+=、(A3)のときは|=という演算子が違うだけ
基本的な計算は一緒。ただし、(A3)はboolで値をもつのをやめ、intで持つことで、計算量を落とせる可能性がある。
(A2)(A3)については、K1個だけではなく、0からKまで、全ての計算結果が使えるのを忘れないように。

■N : 種類数・項数
  (N1) 普通
  (N2) 小さい(N=20以下)
  (N3) それなりに小さい(N=40以下)

まず一番最初にみたい条件。Nが小さい場合は、そもそも総当りだけで解ける可能性がある。例えば、
・N=20で、xが0-1のときは、  2^20= 1048576通り調べればよいだけ。
・N=15で、xが0,1,2のときは、3^15=14348907通り調べればよいだけ。
総当りのおかげで、その他の条件が厳しいときでも、簡単に解ける。逆に見落とすと、悲惨。
Nがそれなりに小さいときは、半分全列挙が使える可能性がある。

■x : 1種類あたりの個数制限
  (x0) 個数制限なし
  (x1) 0-1
  (x2) 個数制限あり(0123とも呼ばれる?)

一番簡単なのは(x1)。DPテーブルの各マスについて、選ぶ選ばないの2回計算すればいいだけ。
次に簡単なのは(x0)。基本的に計算量を減らすために、




(x2)は、個数制限の数字が少なければ、そのまま計算できるのだが。オーダーを落とす方法はさらにアドホックでやらしいかも。
  ・DPの値に表の右にいける回数を入れる。(個数制限つき部分和問題)
  ・テーブルの性質を生かして計算量を減らす(重複組み合わせ)
  ・品物を1+2+4+8+...個ずつに分けて、合体して、品物数を減らす(個数制限つきナップサック問題)

■w,W : 制約条件(重量)
  (W0) 制約条件がない
  (W1) 制約条件がある(Wは普通)
  (W2) 制約条件がある(Wが大きい)
  (W3) 制約条件がある(wが全て1。つまり、条件がΣx=Wの形)

(W2)のときは、vが普通の値であれば「DPの対象の入れ替え」を考えよう。これは、ナップサック問題でも可能。
「○○がX以下で、△△を最大化しなさい→△△がいくらまでなら、○○の最小値はX以下になるか?」
が重要
例えば「重さがW以下で、価値を最大化しなさい→価値がいくらまでなら、重さの最小値はW以下になるか」というふうになる。
wもvも大きければ、総当りを考えよう。
(W3)のときは、そもそもGreedyで解ける可能性があるので注意。
個数制限がそもそもある場合は、(W0)のように制約条件がないパターンもある。

■v,V : 価値
  (V1) vは普通
  (V2) vが大きい
  (V3) vが全て1(つまり、目的関数がΣxの形)

基本的にナップサックでは、dp[][]の値の部分が価値になり、long longまで値をとることは可能なので、心配することはない。
それより、(V3)を見逃す可能性があるのが怖い。Σvxだけでなく、Σxも同種の問題となる。
例えば、お釣りを払うとき、一番コインの枚数が少なくなるような問題は、目的関数がminΣx、制約条件がΣwx=Wとなり、これもDP。
http://en.wikipedia.org/wiki/Change-making_problem
先ほど述べたように、Wが大きくて、Vが小さい問題は、DPの対象の入れ替えも考えること。

▲いままでに見かけた問題

蟻本=プログラミングコンテストチャレンジブック

・(A1)(N1)(x1)(W1)(V1)      01ナップサック問題                ...蟻本P52 →DP。O(nW)。基本
・(A1)(N1)(x0)(W1)(V1)      個数制限なしナップサック問題      ...蟻本P58 →DP。O(nWW)からO(nW)にする
・(A1)(N1)(x0)(W1)(V1)      個数制限なしナップサック問題(min) ...TopCoder SRM357 Div1 250pts Hotel →DP。O(nW)。目的関数がmin{Σvx}で、制約条件がΣwx≧Wと逆になった形。制約条件の符号が逆のためΣwxがいくらでも値をとりうるようにみえるが、ΣwxをW以上に増えすほど目的関数も増えるので意味がない。心配ならWより大きめの値をdpに使うのが無難。
・(A1)(N1)(x1)(W2)(V1)      01ナップサック問題その2           ...蟻本P60 →DP。O(nW)からO(nnv)にする。DPの対象の入れ替えで、max{dp[品物番号][重さ]=価値}+重さ制約の問題を、min{dp[品物番号][価値]=重さ}+制約なしにする。制約はなしなら、価値が無限に取れうるように見えるけど、幸いΣnvが最大なので、ここまでのテーブルを全部計算すればいいだけ。
・(A3)(N1)(x2)(W0)(V1)      個数制限つき部分和問題            ...蟻本P62 →DP。個数制限なしナップサック問題に似てるけど、dpをboolにせず、右に矢印がひける回数を記録しておいて、(x2)の難しさを避ける。
・(A3)(N1)(x2)(W0)(V1)      個数制限なし部分和問題	          ...         →ダイクストラ法。知らないと無理。uwitenpenさんのアドバイス"a_iのうち一番小さい数の剰余で並べていく。たとえば(5,7,9)だったら01234\n56789\nみたいに。ここで、どれかひとつの数が表現可能だったら、それ以降の同じ列の数も当然表現可能。つまり、各列で最初に表現可能になる数を求めれば良い。それを求めるのにdijkstraを使うのだ。" nico_shindanninさんの返答 "各列をノードにみたてて、行の移動量を距離にみたてたリンクを張って、各ノードの最短距離を足したのが答え?"

CodeCraft 11    INTCOMB  http://www.spoj.pl/problems/INTCOMB/
POJ             Elevator http://poj.org/problem?id=3539
Google Code Jam Fence    http://code.google.com/codejam/contest/dashboard?c=639102#s=p1

・(A2)(N1)(x2)(W0)(V3)      重複組合せ                        ...蟻本P67 →DP。O(nmm)からO(nm)にする方法は、ちょっと特殊。パスカルの三角形っぽいものができる。区間の和を求めるため、+だけでなく-も使うのがポイント。
・(A2)(N1)(x1)(W0)(V3)      組合せ                                       →DP。上の特殊ケース。パスカルの三角形ができる。
・(A1)(N1)(x1)(W3)(V1)      重さが等しい0-1ナップサック問題   ...        →Greedy。これは選ぶ選ばないケースの差をみて、差の大きい順でソートしてGreedyでOK。DP不要。重さが等しいので、価値がより増えるものから選ぶのは当然。
・(A1)(N1)(x1)(W1)(V1)(??)  順序つき 0-1ナップサック          ...TopCoder SRM502 Div1 500pts TheProgrammingContestDivOne  →DP+Greedy?。通常はxを選ぶ順序が関係する問題は解けない。ただし、正しい順序で選ぶことで、最適性原理をまだ満たしているのであれば、使用可能。
・(A1)(N1)(x1)(W3)(V1)      巨大ナップサック                  ...蟻本P148→総当り。半分全列挙。
・(A1)(N1)(x0)(W1)(V1)      個数制限つきナップサック問題      ...蟻本P284 →DP。O(nmW)をO(nW)で解く方法はまだ理解してない…。O(nWlogm)で解く方法は、品物の選べる数mを1+2+4+8のように分解して、品物の種類をnlog(m)の0-1ナップサック問題にする。
・Change-making problem
・2制約条件