0/1 Knapsack Problem
n個の品物があります。品物iの重さはweights[i]で、価値はvalues[i]です。バッグに入れられる重さの合計は最大でcapacityです。各品物は1つずつしかなく、丸ごと入れるか、入れずに残すかのどちらかです。バッグに入れられる価値の合計の最大値を返してください。
関数
- weightsinteger-array
- 各項目の重み
- valuesinteger-array
- 各項目の値
- capacityinteger
- バッグが運べる最大重量
- 戻り値integer
- 容量内に収まる重さのアイテムの合計価値の最大値
制約
1 ≤ n ≤ 100、ここでn = weights.length = values.length1 ≤ weights[i] ≤ 10001 ≤ values[i] ≤ 1041 ≤ capacity ≤ 1000
例
- 入力
- weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
- 出力
- 17
- 説明
- 品物0と2の重さは4 + 3 = 7で、価値は10 + 7 = 17です。最も価値の高い品物（重さ5、価値12）を最初に詰めると、品物1だけを入れる余地が残り、合計は16になります。
- 入力
- weights = [5, 4, 3]values = [10, 7, 6]capacity = 7
- 出力
- 13
- 説明
- アイテム1と2の重さは4 + 3 = 7で、価値は7 + 6 = 13です。アイテム0は重さ1単位あたり2の価値があり、どのアイテムにも劣りませんが、それを選ぶと残りの2単位には何も入りません。
- 入力
- weights = [6, 8]values = [5, 9]capacity = 5
- 出力
- 0
- 説明
- どちらの品物も重さが5を超えているため、入るものはなく、空のバッグの価値は0です。
発展問題
容量が10^9に達する一方で、値の合計が最大でも10^4だとします。テーブルは何を基準にインデックス付けしますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
項目0から始めて、順番に項目を決めます。それを詰める場合も残す場合も、その後の項目について同じ問題に直面します。その問題で変わるのはどの数字ですか？
ここから先の最適な値は、2つの数値だけで決まります。今見ている項目と、残りの容量です。項目が100個、容量が1000の場合、このような組み合わせは約10^5個あるため、それぞれを一度計算して保存できます。
容量
cが 0 からcapacityまでのそれぞれについてbest[c]を保持し、最初はすべて 0 にします。重さw、価値vの品物について、cをcapacityからwまで降順にたどり、best[c]とbest[c-w] + vの大きい方を保持します。降順にたどることで、品物が 2 回詰め込まれるのを防ぎます。
解説
どの貪欲な順序もうまくいきません。最も価値の高い品物を最初に詰めても、最初の例では17ではなく16になります。品物 i 以降から得られる最良の価値は、i と残り容量（最大1000の整数）だけで決まります。各組に表のセルを1つ使えば O(n × capacity) となり、容量を大きい方から順にたどれば1行だけで十分です。
各項目について両方の選択肢を試してください
正しいが、最大のテストでは終わらない
考え方
best(i, room)を、空き容量がroom単位あるときに、項目i以降から追加できる品物の最大価値とします。最後の項目を過ぎた場合は0です。項目iをスキップすると、best(i+1, room)になります。weights[i] ≤ roomの場合にその品物を詰めると、values[i] + best(i+1, room-weights[i])になります。大きい方を選びます。収まるすべての詰め方は、詰めるかスキップするかの選択を並べた1つの列であり、再帰処理はそのすべてを試します。
品物が1つ増えるごとに、経路の数は2倍になります。重さがそれぞれ10で、容量が1000のバッグのように、100個の品物がすべて一緒に収まる場合、経路は2^100通りになります。
アルゴリズム
best(i, room)を書き、iが最後の項目を過ぎている場合は0を返します。skipにbest(i+1, room)を設定します。weights[i] > roomの場合は、skipを返します。- それ以外の場合は、
skipとvalues[i] + best(i+1, room-weights[i])の大きい方を返します。 best(0, capacity)を返します。
def knapsack(weights, values, capacity):
n = len(weights)
# The most value items i, i+1, ... can add with room units of weight left
def best(i, room):
if i == n:
return 0
skip = best(i + 1, room)
if weights[i] > room:
return skip
take = values[i] + best(i + 1, room - weights[i])
return max(skip, take)
return best(0, capacity)項目と容量ごとに表を埋める
考え方
再帰では、多くの経路で同じ組 (i, room) に到達します。組の数は最大でも 101 × 1001、約 10^5 なので、それぞれを一度だけ計算します。
best[i][c] を、最初の i 個の品物を容量 c のナップサックに入れたときの最大価値とします。行 0 はすべて 0 です。重さ w、価値 v の品物 i-1 について、入れない場合は best[i-1][c] となり、w ≤ c のときに入れる場合は best[i-1][c-w] + v となります。行 i が参照するのは行 i-1 だけなので、各品物は各セルに最大 1 回だけ反映されます。
最初の例では、品物 2（重さ 3、価値 7）を入れると、容量 7 のときの値は best[2][4] + 7 = 17 になります。続いて品物 3 を入れる場合の値は best[3][2] + 12 = 16 にしかならないので、答えは 17 のままです。
アルゴリズム
- n+1 行、capacity+1 列の表を作り、すべて 0 にします。
- 1 から n までの各行
iについて、w = weights[i-1]とv = values[i-1]を取り出します。 - 各容量
cについて、best[i][c]にbest[i-1][c]を設定します。 w ≤ cかつbest[i-1][c-w] + vのほうが大きい場合は、代わりにその値を格納します。best[n][capacity]を返します。
def knapsack(weights, values, capacity):
n = len(weights)
# best[i][c]: the most value from the first i items within capacity c
best = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
best[i][c] = best[i - 1][c] # leave item i-1 out
if w <= c and best[i - 1][c - w] + v > best[i][c]:
best[i][c] = best[i - 1][c - w] + v # put it in
return best[n][capacity]1行、容量を下方向にたどる
考え方
行 i に必要なのは行 i-1 だけなので、1行分の best[c] を保持し、アイテムごとに上書きします。走査する方向によって答えが正しいかどうかが決まります。
c を小さい方から大きい方へ走査すると、best[c-w] には現在のアイテムがすでに含まれている可能性があります。重さが 3、価値が 5 のアイテムが1つあり、容量が 6 の場合、容量 3 の価値は 5 になり、その後、容量 6 の計算でその値を読み取って 10 になります。つまり、2個分です。capacity から w まで大きい方から小さい方へ走査すると、読み取るセルは書き込むセルより下にあり、後から上書きされるため、前の行の値を保持したままです。
アイテムを無制限に複数個選べる場合は、小さい方から大きい方への走査が正しいループです。ここでは、時間計算量は O(n × capacity) のまま、メモリ使用量は1行分に減ります。
アルゴリズム
- すべて0の、
capacity + 1個の要素を持つbestを作ります。 - 重さが
w、価値がvの各品物について、cをcapacityからwまで減らしながら進めます。 best[c-w] + vがbest[c]を上回る場合、その値をbest[c]に格納します。best[capacity]を返します。
def knapsack(weights, values, capacity):
# best[c]: the most value from the items seen so far within capacity c
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Walk the capacities downward so each item goes in at most once
for c in range(capacity, w - 1, -1):
if best[c - w] + v > best[c]:
best[c] = best[c - w] + v
return best[capacity]
落とし穴と境界ケース
- 1行バージョンで容量を小さい方から順に処理すると、アイテムを2回詰めてしまいます。重さ3、価値5のアイテム1つを容量6のバッグに入れると、5ではなく10になります。
capacity + 1ではなく、capacity個の要素を持つ行。すると、best[capacity-1]を返した場合、重さ1のアイテムを容量1のバッグに入れるような、バッグをちょうど満たす詰め方が考慮されません。- 初期値を負の無限大にする。バッグは満杯である必要はないため、すべての要素の初期値は0です。負の無限大にすると、3つ目の例では0ではなく負の無限大が返されます。
- バッグより重いアイテムはスキップする必要があります。3つ目の例で閉区間
w...capacityを使うとSwiftではプログラムが停止し、(w+1):(capacity+1)を使うとRでは逆順に数えます。
よくある質問3
0/1ナップサック問題の時間計算量はどれくらいですか？
この表の実行時間は O(n × capacity) で、100個のアイテムと容量1000の場合は約10^5ステップです。また、1行版のメモリ使用量は O(capacity) です。この計算量の上限は擬多項式時間です。容量の桁数ではなく、その値に応じて増加します。一般的な問題はNP困難です。
0/1ナップサック問題では、なぜ貪欲法がうまくいかないのでしょうか？
貪欲法の規則では、選択した品物のために残りの容量が使われずに残ってしまっても、その選択を取り消すことはありません。容量が7の場合、重さ5で価値10の品物は比率が最も高いものと同率ですが、重さ4と3の品物を合わせた価値は13です。比率による貪欲法が最適となるのは、品物を分割できる分数ナップサック問題の場合だけです。
0/1ナップサック問題で、どのアイテムが選ばれたかをどうやって調べますか？
表全体を保持し、best[n][capacity]から逆にたどります。best[i][c]がbest[i-1][c]と異なる場合、アイテムi-1が詰め込まれたことになるので、それを記録し、cからその重さを引きます。そうでなければ、同じcのまま行i-1に移動します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def knapsack(weights, values, capacity):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
weights = [4, 2, 3, 5] values = [10, 4, 7, 12] capacity = 7
期待される出力
17