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 で表を作るときは、行の作り方に落とし穴があります。

dp = [[0] * 6] * 4      # 4 行が同じ 1 本を指してしまう
dp[1][2] = 3
print(dp[0][2])         # 3 になる

dp = []
for row in range(4):
    dp.append([0] * 6)   # 毎回別の行を作る
dp[1][2] = 3
print(dp[0][2])         # 0 のまま

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

やってみよう

ひな形の TODO を完成させてください。取らない値と、取る場合の価値の比較更新を自分で書きます。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

例は重さ 3、価値 8 の品物を容量 5 で検討する場面です。取る場合は、前の行の容量 2 の答えに 8 を足します。取らない場合は前の行の容量 5。その二つを比べます。表は普通の for で別々の行を確保してあり、内包表記を使いません。演習ではこの二つの候補と比較更新を書きます。

1. 取らない値と、取る場合の価値の比較更新を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える