- 記入中
- 参照元
- 答え
ナップサック問題
運べる重さには限りがあり、どの品物にも重さと価値があります。最も多くの価値を運ぶには、どの品物を選べばよいでしょうか。すべての組み合わせを試すと、品物が1つ増えるごとに手間が2倍になります。品物を行、容量を列にした表なら、1マスずつ最良の詰め方を見つけられます。 品物をタップするとナップサックに入り、もう一度タップすると(ナップサックの中でも棚の上でも)取り出せます。ナップサックは重さで満ちていき、タイルには入れたドルと最大価値が並んで表示されます。「最適な詰め方」を押すと最適なナップサックが見られます。パネルでは品物のキログラムとドルを変えたり、品物を追加・削除したり、ナップサックの容量を設定したりできます。「表」ビューでは、動的計画法が最適なナップサックをどう見つけるかがわかります。「再生」を押すと表が埋まっていく様子が見られ、「ステップ」と「戻る」で1ステップずつ進めたり戻したりできます。ステップのスライダーをドラッグすると好きな場所に移れます。各行で品物が1つ加わり、各列はキログラム単位の容量で、各マスには入りきる最大のドルが入ります。表を選択しているときは、矢印キーで1ステップずつ動き、スペースキーで再生と一時停止、Home キーと End キーで最初と最後に移動します。
使い方
- 品物の箱をタップしてナップサックに詰め、重さ(キログラム)でいっぱいになっていく様子を見ましょう。
- ドルで表した最高の価値を目指すか、「最適な詰め方」を押して一番よい詰め方を見てみましょう。
- 「表」表示を開いて再生を押し、各マスが品物を詰めるか残すかを選ぶ様子を見ましょう。
表のしくみ
各行で品物が1つずつ加わり、各列は 0 からナップサックの容量までの容量を表します。マスには、その行までの品物を使ってその容量に入る最大の価値が入ります。新しい品物を使わない場合は、上のマスの値です。使う場合は、入るなら、その品物の価値に残りの重さに対する最大価値を足したもので、その値は1つ上の行で品物の重さの分だけ左にあります。マスには2つのうち大きい方が入ります。品物のない最初の行はすべて 0 です。
品物を逆にたどる
右下のマスが最大価値です。品物を見つけるには、そこから始めて上のマスと比べます。同じなら、最後の品物は不要でした。大きければその品物はナップサックに入っているので、その重さを引いてその列に移ります。最初の行に着くまで、毎回1行ずつ上がります。アプリはこの逆たどりをオレンジ色で示し、入れた品物を表の下に一覧表示します。
よくある質問
0/1 ナップサック問題の「0/1」とはどういう意味ですか?
各品物は1回入れるか、まったく入れないかのどちらかで、一部だけ入れることも2回入れることもありません。米粒のように品物を分けられるなら、重さあたりの価値が高いものから入れるのが最適です。これは分数ナップサック問題と呼ばれます。
なぜ重さあたりの価値が高いものから入れないのですか?
品物を丸ごと入れると、すき間が残ることがあるからです。容量が 7 で、重さ 1、3、4、5、価値 1、4、5、7 の品物があるとき、重さあたりの価値が最も高いのは重さ 5 の品物ですが、それを入れると重さ 1 の品物の分しか余裕がなく、合計は 8 です。重さ 3 と 4 の品物を合わせると価値は 9 になります。
ナップサック問題のアルゴリズムはどれくらい速いですか?
表には(品物の数 + 1)×(容量 + 1)個のマスがあり、それぞれ1ステップで埋まります。容量が小さければ速いですが、容量はとても大きな数になりうるので、この問題は一般には NP 困難です。この表を使う方法は擬多項式時間のアルゴリズムと呼ばれます。
同じ品物を2回入れられますか?
ここではできません。個数制限なしナップサック問題では、各品物を何回でも選べます。その場合、表は1つ上の行ではなく同じ行の左のマスを読みます。硬貨の両替のアプリと同じです。
データがどこかに送信されますか?
いいえ。計算はすべてブラウザー内で行われ、最後の設定はこのブラウザーのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ