品物を一度だけ選ぶ
容量5の袋へ、重さ2・価値3、重さ3・価値4、重さ4・価値5の三品物を入れます。各品物を選ぶか選ばないかの二択で、同じ品物を何度も使うことはできません。最適は最初の二つで、重さ5・価値7です。価値が最大の一品を選ぶだけでは5、価値を重さで割った順に選ぶ方法も、一般に最適解を保証しません。分割可能な品物を扱う問題とは前提が異なります。
ここでは重さを正の整数、容量を非負の整数、価値を整数として、何も選ばない選択を許します。負の価値の品物も選ばなければよいので、初期の最良値は0です。重さ0を許す別仕様も設計できますが、今回の実装は拒否します。問題の名前だけで、重量の単位や品物の再使用、空の選択の可否まで決まったと考えないようにします。
品物の接頭辞と残る容量で分ける
dp[i][c]を「最初のi品物だけを使い、重さc以下で得られる最大価値」と定義します。ちょうどcを使うという意味ではありません。i番目を選ばないならdp[i−1][c]、選ぶなら重さwがc以下のときdp[i−1][c−w]+vです。両者の大きい方を取ります。前の行を参照するため、今見ている品物を同じ段階で二回使いません。
最初の品物までで容量2以上の値は3、二品物までなら容量5で7になります。容量3では二番目の価値4を選ぶ方が良く、容量4では三番目の価値5が候補となりますが、容量5の7を上回りません。表の行ごとに使える品物の集合が増えることと、列ごとに許される重さが変わることを区別します。小さな表を手で埋めると、遷移式の参照先が具体的になります。
| 使える品物 / 容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| なし | 0 | 0 | 0 | 0 | 0 | 0 |
| (2,3)まで | 0 | 0 | 3 | 3 | 3 | 3 |
| (3,4)まで | 0 | 0 | 3 | 4 | 4 | 7 |
| (4,5)まで | 0 | 0 | 3 | 4 | 5 | 7 |
選んだ品物を表から戻す
最大価値だけでなく採用品物を返すため、最後の行の容量5から逆へたどります。dp[i][c]が前の行と同じなら、その品物を選ばない解を採用できます。異なれば品物i−1を記録し、その重さをcから引いて前の行へ進みます。同じ価値の解が複数あっても、今回は前の行と同値なら選ばない規則で一つの解を返します。全ての最適解を列挙する契約ではありません。
掲載コードは、短い品物列と容量0〜8で、全ての採否の組合せを列挙した参照解へ価値を一致させます。採用品物の総重量も容量以下かを検査します。空の品物列なら価値0・空リストです。復元したリストの価値を再計算する検査も加えれば、最大値の表と選択経路の対応をさらに確認できます。表の値が正しいことと、復元が正しいことは別の観測です。
from itertools import product
def knapsack(items,capacity):
if capacity<0 or any(w<=0 for w,v in items):raise ValueError('positive weights required')
dp=[[0]*(capacity+1) for _ in range(len(items)+1)]
for i,(weight,value) in enumerate(items,1):
for c in range(capacity+1):
dp[i][c]=dp[i-1][c]
if weight<=c:dp[i][c]=max(dp[i][c],dp[i-1][c-weight]+value)
chosen=[];c=capacity
for i in range(len(items),0,-1):
if dp[i][c]!=dp[i-1][c]:chosen.append(i-1);c-=items[i-1][0]
return dp[-1][-1],sorted(chosen)
items=[(2,3),(3,4),(4,5)];assert knapsack(items,5)==(7,[0,1])
for count in range(5):
items=[(i+1,(i*3)%7) for i in range(count)]
for capacity in range(9):
reference=max(sum(v*t for (w,v),t in zip(items,mask)) for mask in product([0,1],repeat=count) if sum(w*t for (w,v),t in zip(items,mask))<=capacity)
value,chosen=knapsack(items,capacity);assert value==reference
assert sum(items[i][0] for i in chosen)<=capacity
assert len(chosen)==len(set(chosen))
assert sum(items[i][1] for i in chosen)==value
print('example value=7 items=0,1; brute-force comparisons passed')
一次元へ縮めるときは逆順に進める
最大値だけが必要なら、前の行を配列へ上書きして容量の領域をO(W)へ減らせます。ただし容量を大きい方から小さい方へ更新します。容量を小さい方から進めると、今の品物で更新したdp[c−w]を同じ品物の処理中に再利用し、同じ品物を二回選ぶことがあります。重さ2・価値3の一品と容量4なら、誤った順方向更新が価値6を作るのが反例です。
逆順なら、参照する小さい容量はまだ前の段階の値です。この理由を理解せず、配列を一つにした後も二次元と同じ見た目の式だから正しい、と判断しないでください。採用品物も返す場合、上書き後の一配列だけから履歴を復元するには追加の工夫が必要です。領域を節約した版と、読みやすい二次元表の版を、必要な出力と実装の検証しやすさで選びます。
容量の数値と入力の長さを分ける
品物数をn、容量の整数値をWとすると、二次元の基本形は時間O(nW)、領域O(nW)です。容量が小さいと扱いやすい一方、Wが十億なら表をそのまま作るのは現実的でない場合があります。Wを二進表現する入力はO(log W)ビットで書けるので、O(nW)を入力のビット長に対する多項式時間と呼ぶことはできません。この違いが擬多項式という表現の意味です。
重さに小数があるからといって、無制限に細かい単位へ変換してよいわけでもありません。0.001単位へ変えれば容量の列数も増えます。価値側を軸にするDP、品物数が小さい場合の分割、近似など、条件へ応じた別の選択肢を検討します。今回の教材は全ての大規模な最適化問題を解く万能な実装ではなく、状態の定義と一度だけ選ぶ遷移を学ぶための基本形です。
別問題へ変わる条件を見抜く
品物を何度も使えるなら、0–1の契約ではなく無制限ナップサックです。品物を分割できるなら、価値密度の順に選ぶ別の性質を使える場合があります。各種類を三個まで使える場合も、採否二択だけでは表現できません。似た表へ少し式を足す前に、どの選択を許すかを整理します。反例の一品を二回選ぶ挙動も、別仕様では正解になり得ます。
容量を必ず使い切る課題では、初期値を全て0へしてしまうと、到達できない重さと価値0の到達状態を区別できません。負の無限大に相当する未到達の印などが必要です。今回の「容量以下」と「ちょうど容量」は違う状態定義です。問題文の一語が変わった場合でも、dp[i][c]の意味、初期条件、遷移、返す値を一式で更新し、古いテストの成功だけで正しさを引き継がないでください。
復元した添字が重複していないこと、選んだ価値の合計がDPの最適値と一致することも検査します。容量内に収まるだけでは、最適解を復元した確認にはなりません。
復元した値をもう一度計算する
採用した添字から重さと価値を再計算し、容量以下で最大値の表と同じ価値になることを確認します。重さだけを検査しても、何も選ばないリストを誤って返す復元の不具合を見逃す場合があります。添字が重複していないことも、0–1という意味へ対応する条件です。
同じ最適価値を持つ解が複数あるとき、特定の添字列だけを正解に固定すると、別の正しい復元を誤って失敗にする可能性があります。入力例で一つの答えを示すことと、試験が許す解の集合を区別します。重さ、価値、重複、参照解の最大値を検査すれば、同値の候補へ不必要な順序の制約を付けずに正しさを確認できます。
採用と非採用の二択を解く課題
課題は品物(重さ1,価値2)、(重さ3,価値5)、(重さ4,価値6)、容量4です。解答は最初と二番目を選び価値7です。最後の一品だけなら6で、一番価値の高い品物を単独で選ぶ規則は最適になりません。最後の行の容量4で、三番目を選ぶ候補6と、選ばない前行の7を比較する様子を表へ書いてください。
追加課題は、重さ2・価値3の一品、容量4を一次元の順方向更新で処理する場合です。容量2で3を書き、容量4でその3をもう一度使うため6となります。しかし0–1問題の正解は3です。解答では、数値が大きすぎたことだけでなく、参照したdp[2]が前の品物段階ではなく現在の段階の値だったと説明します。配列の更新方向が状態の時間軸を守るために必要だと確認してください。