アルゴリズムと計算量の問題
次の 個の品物から、重さの合計が 以下になるようにいくつかを選びます。各品物は選ぶか選ばないかのどちらかで、同じ品物を 個以上選ぶことはできません。
| 品物 | A | B | C | D |
|---|---|---|---|---|
| 重さ | ||||
| 価値 |
品物を A, B, C, D の順に 番目とし、 番目の品物の重さを 、価値を とします。 を「 番目から 番目までの品物だけを使い、重さの合計が 以下になるように選んだときの価値の合計の最大値」と定めます（）。漸化式
（ただし のときは ）を用いて表を埋め、選んだ品物の価値の合計の最大値 を求めてください。
この問題で使うもの
- 0-1 ナップサック問題の動的計画法（説明と入口の問題）
この問題を解けるようになるまで（2 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る（前提が先）
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
0-1 ナップサック問題の動的計画法を使います。品物を 1 つずつ増やしながら、容量 ごとの最大価値 を表に埋めていきましょう。
ヒント 2
各マスでは「 番目の品物を入れない：」と「入れる：」の大きい方をとります。 のときは入れられないので です。
ヒント 3
A, B, C まで使った行は （）になります。最後に D（重さ , 価値 ）について を計算しましょう。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
を 、 について順に埋めます。 番目の品物について「入れない」場合が 、「入れる」場合が で、その大きい方をとります。
：品物がないので （）。
（A：）： では 。 では 。
（B：）： は前の行と同じ 。
- ：
- ：
- ：
- ：
- ：
（C：）： は 。
- ：
- ：
- ：
- ：
- ：
- ：
- ：
（D：）： は前の行と同じ。
- ：
- ：
- ：
- ：
まとめると次の表になります。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 |
| 2 | 0 | 0 | 0 | 5 | 6 | 6 | 6 | 11 | 11 |
| 3 | 0 | 0 | 3 | 5 | 6 | 8 | 9 | 11 | 11 |
| 4 | 0 | 0 | 3 | 5 | 6 | 8 | 9 | 11 | 13 |
よって です。最後の計算で が選ばれたので D を入れ、残り容量 では より A を入れています。つまり A と D を選ぶと重さ 、価値 となり、これが最大です。
別解
品物は (重さ, 価値) = A(3,5), B(4,6), C(2,3), D(5,8)。 を について順に求める。
: 0,0,0,0,0,0,0,0,0
(A: 3,5): は 0、 は 5。
: 0,0,0,5,5,5,5,5,5
(B: 4,6):
- : と同じで 0,0,0,5
- :
- :
- :
- :
- :
: 0,0,0,5,6,6,6,11,11
(C: 2,3):
- : 0,0
- :
- :
- :
- :
- :
- :
- :
: 0,0,3,5,6,8,9,11,11
(D: 5,8):
- : 0,0,3,5,6
- :
- :
- :
- :
よって 。
検算: A と D を選ぶと重さ 、価値 。他の組合せを確認すると、B+C=6 で価値 9、A+B=7 で 11、A+C+...=5 で 8、B+C+... 重さ超過、A+B+C=9 は超過。D+C=7 で 11、D+A=8 で 13。13 が最大。