0-1 ナップサック問題の動的計画法

品物と容量の 2 次元の表 $V [i] [w] = max (V [i - 1] [w], V [i - 1] [w - w_{i}] + v_{i})$ を埋めて、容量以下での価値の合計の最大値を求められる

前提

動的計画法の基本（硬貨の最小枚数）（大学数学アルゴリズムと計算量）

説明

重さと価値が決まった品物が $n$ 個あり、それぞれを「入れる」か「入れない」かを選びます。重さの合計が容量 $W$ 以下という条件のもとで、価値の合計の最大値を求めるのがこの技能です。各品物は 1 回までしか使えないため、0-1 ナップサック問題と呼ばれます。ここでは品物 $i$ の重さ $w_{i}$ と容量 $W$ がどれも 0 以上の整数であると仮定します（価値 $v_{i}$ は整数でなくてもかまいません）。予算内での投資の選び方や、時間内に解く問題の選び方など、限られた資源の配分を最適化する場面で使います。

なぜそうしてよいのか

硬貨の問題では、状態は「払う金額 $n$ 」だけで足りました。同じ硬貨を何枚でも使えたからです。ナップサックでは各品物を 1 回しか使えません。そのため「どの品物まで検討したか」も状態に含める必要があります。そこで $V [i] [w]$ を「品物 $1, \dots, i$ だけを使い、重さの合計を $w$ 以下にしたときの価値の合計の最大値」と定めます（ $0 \leq i \leq n$ 、 $w$ は $0 \leq w \leq W$ の整数）。重さ $w_{i}$ と容量 $W$ が 0 以上の整数なので、容量の値としては $0, 1, \dots, W$ の整数だけを考えれば足ります。さらに $w_{i} \leq w$ のとき $w - w_{i}$ も $0$ 以上 $W$ 以下の整数になるので、 $V [i - 1] [w - w_{i}]$ は表の中のマスを指します。品物を 1 つも使わなければ価値は 0 なので、 $V [0] [w] = 0$ です。

品物 $1, \dots, i$ から選ぶ最適な選び方を考え、品物 $i$ を入れるかどうかで場合を分けます。入れない場合、残りは品物 $1, \dots, i - 1$ から容量 $w$ 以下で選ぶ問題なので、最大値は $V [i - 1] [w]$ です。入れる場合は $w_{i} \leq w$ が必要です。品物 $i$ の分の容量 $w_{i}$ を差し引くと、残りは品物 $1, \dots, i - 1$ から容量 $w - w_{i}$ 以下で選ぶ問題になるので、最大値は $V [i - 1] [w - w_{i}] + v_{i}$ です。最適な選び方はこの 2 つの場合のどちらかに必ず入ります。よって $w_{i} \leq w$ のとき $V [i] [w] = max (V [i - 1] [w], V [i - 1] [w - w_{i}] + v_{i})$ 、 $w_{i} > w$ のとき $V [i] [w] = V [i - 1] [w]$ が成り立ちます。

この式の右辺は 1 つ上の行（品物 $i - 1$ まで）だけを参照します。そのため、行 $0$ から順に埋めれば、必要な値はいつもすでに求まっています。また、上の行を見ることで「品物 $i$ は 1 回だけ使う」ことが保証されます。表のマスは $(n + 1) (W + 1)$ 個あり、1 マスあたり定数回の計算で済みます。

手順

表を用意する：行 $i = 0, 1, \dots, n$ 、列 $w = 0, 1, \dots, W$ （整数）の表 $V [i] [w]$ を作る
初期値を入れる：すべての $w$ について $V [0] [w] = 0$
行 $i = 1, \dots, n$ を順に、各行では $w = 0, \dots, W$ を埋める。 $w < w_{i}$ なら $V [i] [w] = V [i - 1] [w]$ （品物 $i$ は入らない）
$w \geq w_{i}$ なら $V [i] [w] = max (V [i - 1] [w], V [i - 1] [w - w_{i}] + v_{i})$ を計算する（入れない場合と入れる場合の大きい方）
最後に $V [n] [W]$ を読む。これが容量 $W$ 以下での価値の合計の最大値

例題

容量 $W = 6$ のナップサックに、次の 3 個の品物から選んで入れる。品物 1：重さ 2・価値 3、品物 2：重さ 3・価値 4、品物 3：重さ 4・価値 6。各品物は高々 1 個しか入れられない。重さの合計が 6 以下となるときの価値の合計の最大値を、動的計画法で求めよ。

例題の解答

重さと容量はすべて 0 以上の整数なので、列は $w = 0, \dots, 6$ の整数で足りる。
【手順 1・2】行 $i = 0, \dots, 3$ 、列 $w = 0, \dots, 6$ の表を作り、行 0 をすべて 0 にする： $V [0] = (0, 0, 0, 0, 0, 0, 0)$ 。
【手順 3・4】 $i = 1$ （ $w_{1} = 2, v_{1} = 3$ ）。 $w = 0, 1$ は $w < 2$ なので上の行をそのまま写し、0 と 0。 $w \geq 2$ では $max (0, V [0] [w - 2] + 3) = 3$ 。よって $V [1] = (0, 0, 3, 3, 3, 3, 3)$ 。
$i = 2$ （ $w_{2} = 3, v_{2} = 4$ ）。 $w = 0, 1, 2$ は上を写して $0, 0, 3$ 。 $w = 3$ ： $max (V [1] [3], V [1] [0] + 4) = max (3, 4) = 4$ 。 $w = 4$ ： $max (3, V [1] [1] + 4) = max (3, 4) = 4$ 。 $w = 5$ ： $max (3, V [1] [2] + 4) = max (3, 7) = 7$ 。 $w = 6$ ： $max (3, V [1] [3] + 4) = max (3, 7) = 7$ 。よって $V [2] = (0, 0, 3, 4, 4, 7, 7)$ 。
$i = 3$ （ $w_{3} = 4, v_{3} = 6$ ）。 $w = 0, \dots, 3$ は上を写して $0, 0, 3, 4$ 。 $w = 4$ ： $max (V [2] [4], V [2] [0] + 6) = max (4, 6) = 6$ 。 $w = 5$ ： $max (7, V [2] [1] + 6) = max (7, 6) = 7$ 。 $w = 6$ ： $max (7, V [2] [2] + 6) = max (7, 9) = 9$ 。よって $V [3] = (0, 0, 3, 4, 6, 7, 9)$ 。
【手順 5】 $V [3] [6] = 9$ が答えになる。 $9 = V [2] [2] + 6$ で、 $V [2] [2] = 3$ は品物 1 によるものなので、選び方は品物 1 と品物 3（重さ $2 + 4 = 6 \leq 6$ 、価値 $3 + 6 = 9$ ）とわかる。

答え: $9$

よくある誤り

漸化式で同じ行を参照し、 $V [i] [w] = max (V [i - 1] [w], V [i] [w - w_{i}] + v_{i})$ としてしまう誤り。こうすると品物 $i$ を何度でも使えることになる。例題では $V [1] [4] = V [1] [2] + 3 = 6$ となり、品物 1 を 2 回使った値が出てしまう。正しくは上の行の $V [i - 1] [w - w_{i}] + v_{i}$ を参照する。
$w < w_{i}$ の列でも $V [i - 1] [w - w_{i}]$ を計算しようとして、負の添字を参照してしまう誤り。品物 $i$ が入らない列では、正しくは $V [i] [w] = V [i - 1] [w]$ とそのまま写す。
価値÷重さの大きい順に入れる貪欲法で答えを出してしまう誤り。たとえば容量 4 で、品物 A（重さ 3・価値 4、比 $\approx 1.33$ ）と品物 B・C（各重さ 2・価値 2.5、比 $1.25$ ）があるとする。比の大きい A を先に入れると、残り容量 1 には何も入らず価値は 4 になる。正しくは B と C を入れた $5$ が最大で、表を埋めれば必ず最大値が得られる。
「容量 $W$ 以下」と「ちょうど $W$ 」を混同する誤り。 $V [0] [w] = 0$ （すべての $w$ ）から始めると $V [n] [W]$ は「 $W$ 以下」での最大値になる。ちょうど $W$ を求めたいなら、初期値を $V [0] [0] = 0$ 、 $w \geq 1$ で $V [0] [w] = - \infty$ と変える必要がある。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

品物	A	B	C	D
重さ	$3$	$4$	$2$	$5$
価値	$5$	$6$	$3$	$8$

品物	A	B	C	D
重さ	$3$	$4$	$2$	$5$
価値	$5$	$6$	$3$	$8$

品物	A	B	C	D
重さ	$3$	$4$	$2$	$5$
価値	$4$	$5$	$3$	$7$

この技能を使う問題

難易度 3（期末試験の応用レベル）
次の $6$ 個の品物から、重さの合計が $12$ 以下になるようにいくつか選ぶ（各品物は選ぶか選ばないかのどちらかで、同じ品物を $2$ 個以上選ぶことはできない）。
品物 A B C D E F
重さ $3$ $4$ $5$ $2$ $6$ $7$
価値 $7$ $9$ $12$ $5$ $14$ $17$
選んだ品物の価値の合計の最大値を求めよ。