0/1 ナップサック問題

容量の決まったリュックに品物を詰めます。品物にはそれぞれ重さと価値があり、同じ品物は 1 個しか入れられません。合計の重さが容量を超えない範囲で、価値の合計を最大にするのが目標です。

価値の高い順に詰めると、9 になるはずが 6 で終わる

重さと価値が (3, 4)、(4, 5)、(5, 6) の 3 個、容量が 7 だとします。価値の高い順に詰めると、まず (5, 6) が入って残り容量は 2。もう何も入らず、価値は 6 で終わりです。実際には (3, 4) と (4, 5) を入れれば重さちょうど 7、価値は 9 になります。

前回のコイン両替と似た失敗ですが、事情が 1 つ増えています。コインは同じ額面を何枚でも使えましたが、今回は各品物が 1 個限りです。「その品物をまだ使っていないか」を覚えていないと、同じものを二重に数えてしまいます。

覚えることが 2 つある

コイン両替では、金額さえ決まれば最小枚数が決まりました。今回は、残り容量が同じでも、そこまでにどの品物を使ったかで答えが変わります。そこで覚える状態を 2 つにします。何個目までの品物を検討したか、そして容量がいくつか、の 2 つです。

品物を 1 個ずつ検討し、それぞれについて取るか取らないかを決めます。取らなければ、価値は 1 個前まで検討したときと同じです。取るなら、その品物の重さぶんだけ容量を空けた状態での価値に、その品物の価値を足します。大きいほうを残します。

表を 1 マスずつ埋める

重さと価値が (2, 3)、(3, 4)、(4, 6) の 3 個、容量 5 で埋めてみます。行が「何個目まで検討したか」、列が「容量」です。

3 行目の容量 5 のマスを見てください。(3, 4) を取らなければ、真上の 3 がそのまま入ります。取るなら、重さ 3 を空けた容量 2 の 1 行上のマスが 3 なので、そこへ価値 4 を足して 7。大きいほうの 7 が入ります。

どのマスも、見に行く先は 1 行上だけです。上の行から順に、左から右へ埋めていけば、参照先は必ず埋まっています。欲しい答えは右下のマスです。

Python で表を作るときは、行の作り方に落とし穴があります。

掛け算で行を増やすと、同じリストへの参照が 4 つ並ぶだけです。1 行書き換えると全行が変わります。

やってみよう

knapsack(weights, values, capacity) を書いてください。行が品物の個数、列が容量の表を用意し、上の行から順に埋めます。i 行目が担当するのは i 番目の品物ですが、配列の添字は 0 から始まるので、対応する重さは weights[i - 1] です。このずれが最も多い間違いです。最後に右下のマスを返します。

1. 各品物は最大 1 個までしか取らない (0/1 ナップサック)
2. dp[i][w] を「i 個まで考えたときに容量 w で実現できる最大価値」と定義し、2 次元配列を埋める
3. 遷移は dp[i][w] = max(dp[i-1][w], dp[i-1][w - wi] + vi) (w >= wi のとき)