Combinatorial - 0-1 Knapsack Problem

2546 submissions, 1217 accepted solutions, 769 scorers
※この記事は編集中です。

各品物を「選択する」か「選択しない」かの組み合わせなので、0-1ナップザック問題といわれます。 N 個の各品物について「選択する」か「選択しないか」の全組み合わせを全て調べるアルゴリズムの計算効率は O(2N) となります。N が 20 でおおよそ 1,000,000 の計算量となります。

品物の大きさ w、ナップザックの大きさ W がともに整数であれば、0-1 ナップザック問題は動的計画法により O(NW) の効率で厳密解を求めることができます。

C[i][w] が、大きさ w のナップザックに、i 個目までの品物を考慮した場合の価値の合計の最大値、となるような (N+1) × (W+1) の2次元配列とします。C[i][w] の値は、

  1. C[i - 1][w - (品物 i の重さ)] + (品物 i の価値)、 または
  2. C[i - 1][w]

の大きい方となります。ここで、1. はこの時点で品物 i を選択する、2. はこの時点で品物 i を選択しない、という処理に対応します。ただし、1. の場合は、品物 i の重さが w を超えない場合に限ります。

入力例の具体的な処理の流れを見てみましょう。

Knapsack Problem     ナップザックの大きさ w が 0、または品物の数 i が 0 個の場合は、価値の合計が 0 なので、w = 0i = 0C[i][w] を 0 に初期化します。

Knapsack Problem     大きさが 1 のナップザックに、品物 1 は入れられないので、C[1][1] は 0 となります。 大きさが 2 のナップザックに、品物 1 を入れることができます。ここでは選択した場合は 0 + 4 = 4 (斜めの矢印)、選択しない場合は 0 (縦の矢印)であり、大きい方の 4 を C[1][2] に記録します。大きさが 3, 4, 5 についても同様です。

Knapsack Problem     大きさが 1 のナップザックに、品物 2 は入れられないので、C[2][1] は 0 となります。 大きさが 2, 3, 4, 5 のナップザックに、品物 2 を入れることができます。 C[2][4] に注目してみましょう。ここではC[1][2] + 品物 2 の価値 (= 4 + 5) または C[1][4] (= 4) のいづれか大きいほうを選びます。

Knapsack Problem     大きさが 1 から 5 のナップザックに、品物 3 を入れることができます。同様に C[i][w] は品物を選択する場合と品物を選択しない場合のどちらか最適な方を選びます。選択する場合は、斜めの矢印、選択しない場合は上からの矢印になります。品物 3 の重さが 1 なので、斜めの矢印の幅は 1 になります。

Knapsack Problem     大きさが 1, 2 のナップザックに、品物 4 は入れることができません。容量を超えるとは、斜めの矢印が配列からはみ出してしまうことに相当します。 大きさが 3, 4, 5 のナップザックに、品物 4 を入れることができるので、上記と同様最適な選択を行います。品物 4 の大きさが 3 なので、矢印の幅は 3 になります。

Knapsack Problem     C[N][W] が価値の最大値となります。ここから、矢印を逆にたどっていくと、選ぶべき品物を特定することができます。斜めの矢印が品物の選択を表しています。


品物の選択情報を配列 G[i][w] に記録することで、最適解における品物の組み合わせを復元することができます。例えば、G[i][w] には、品物 i が選択されたとき DIAGONAL 、選択されなかったとき TOP と記録しておくことで、矢印をたどる過程で選択する品物を出力することができます。

疑似コード

knapsack()
    for w = 0 to  W
        C[0][w] = 0
        G[0][w] = DIAGONAL

    for i = 1 to N
        C[i][0] = 0

    for i = 1 to N
        for w = 1 to W
            if items[i].w <= w
                if  items[i].v + C[i-1][w - items[i].w] > C[i-1][w]
                    C[i][w] = items[i].v + C[i-1][w - items[i].w]
                    G[i][w] = DIAGONAL
                else
                    C[i][w] = C[i-1][w]
                    G[i][w] = TOP
            else
                C[i][w] = C[i-1][w]
                G[i][w] = TOP

Reference

 

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ)

AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。