ナップサック問題
重さの制限がある登山者、袋を持った泥棒、予算とプロジェクトの一覧を抱えた会社。どれも同じ問いに向き合っています。上限を超えずに最も多くの価値を得るには、何を入れればよいのか。これがナップサック問題で、重さがほどほどの大きさの整数なら、動的計画法で厳密に解けます。
問題
n 個の品物があり、それぞれに重さと価値があります。また、重さ W までしか入らないナップサックがあります。重さの合計が W 以下で、価値の合計ができるだけ大きくなる品物の組を選びます。各品物は丸ごと入れるか入れないかのどちらかなので、0/1 ナップサック問題と呼ばれます。品物が n 個なら組は 2ⁿ 通りあるので、すべて試すのはすぐに不可能になります。
表
best[i][w] を、最初の i 個の品物だけを使って重さ w に入る最大の価値とします。すると best[0][w] = 0 で、それ以降の各行には2つの選択があります。品物 i を入れずに best[i − 1][w] とするか、その重さ wᵢ が入るなら入れて、その価値に best[i − 1][w − wᵢ] を足すかです。大きい方が best[i][w] です。表を1行ずつ埋めていけば、必要な2つのマスは常に計算済みです。
例
容量を 7 とし、重さ 1、3、4、5、価値 1、4、5、7 の4つの品物を考えます。最初の品物だけなら、1 以上のどの容量でも価値は 1 です。2番目を加えると、容量 4 で両方を入れて 5 になります。3番目を加えると、容量 7 で品物 2 と 3 を入れて 9 になります。4番目の品物は重さ 5、価値 7 で、容量 6 か 7 なら品物 1 と合わせて 8 になりますが、9 の方が良いので右下のマスは 9 です。重さ 3 と 4 の品物を入れます。
どれくらい難しいのか
表には約 n·W ステップが必要です。速そうに見えますが、W は数であり、d 桁の数は最大で 10 の d 乗にもなるので、計算量は入力の長さに対して指数的に増えます。ナップサック問題は NP 困難で、1972 年にリチャード・カープが示した 21 の NP 完全問題の1つでした。実際には、表を使う方法、分枝限定法、優れた近似スキームによって、大きな現実の問題もうまく扱えます。
歴史と応用
この名前は 20 世紀初めの数学者トビアス・ダンツィクにさかのぼり、その息子ジョージ・ダンツィクは 1957 年にこの問題に対する古典的な貪欲法を示しました。ナップサック問題は、予算の配分やポートフォリオの選択、原材料をできるだけ無駄なく切り出すこと、貨物の積み込み、さらには初期の公開鍵暗号にも現れます。1978 年のメルクル・ヘルマン暗号はナップサック問題をもとに作られましたが、数年後に破られました。
試してみよう
アプリを開いて「表」表示に切り替え、「ステップ」を押してください。オレンジ色のマスが埋められているマスで、青いマスはそれが比べる2つのマスです。真上のマスと、1つ上の行で品物の重さの分だけ左にあるマスです。最後のマスのあと、逆たどりが右下の角からオレンジ色で上っていき、入れた品物が表の下に表示されます。
よくある質問
0/1、個数制限付き、個数制限なしのナップサック問題の違いは何ですか?
0/1 版では各品物を最大1回選びます。個数制限付き版では各品物の個数に限りがあり、個数制限なし版では何個でも選べます。表はこれらの間でわずかに変わるだけです。
ナップサック問題で貪欲法が正しいことはありますか?
品物を分けられる分数ナップサック問題では、重さあたりの価値が高いものから選ぶのが最適です。品物を丸ごと扱う場合は大きく外れることもありますが、貪欲法の結果と、最も価値の高い品物1つだけの場合のうち良い方は、常に最大価値の半分以上になります。
表にはどれくらいのメモリが必要ですか?
表全体では (n + 1)·(W + 1) 個のマスが必要で、品物を逆にたどるにはこれが必要です。最大価値だけが知りたいなら、W + 1 個のマスの1行を右から左へ埋めれば十分です。
ナップサック問題は部分和問題と同じですか?
部分和問題は、各品物の価値が重さと等しく、ナップサックをちょうど満たせるかどうかを問う特別な場合です。これも NP 完全で、同じ種類の表で解けます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
ナップサック問題を試す