ナップサック問題

ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物（各々、価値 v_i、重量 w_i）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（x_i ∊ {0, 1}）や、同じ品物をいくつでも入れてよい場合（x_i は0以上の整数）など、いくつかのバリエーションが存在する。

ナップサック問題

決定問題としてのナップサック問題は、「W, v_i, w_i のほかに価値の合計の目標 V が与えられたとき、重量の合計が W 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方が存在するか」を判定することである。 全ての品物について v_i = w_i である場合は、部分和問題と等価であるため、ナップサック問題は部分和問題の一般化である。ナップサック問題は、（部分和問題もそうであるが）NP困難と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全(NPかつNP困難)と呼ばれるクラスにも属する。

解法として、動的計画法を用いた擬多項式時間アルゴリズムや FPTAS の存在が知られており、実用的にはほぼ最適な解が得られる。

定義

$I=\{1,2,\cdots ,N\}$ を品物の集合とし、各品物 $i\in I$ の重みを$w_{i}$、価値を $v_{i}$、品物の重量の合計の上限を $W$ とするとき、次のようにあらわされるものをナップサック問題という。

${\begin{array}{lll}\max &\sum _{i\in I}v_{i}x_{i}&\\\mathrm {s.t.} &\sum _{i\in I}w_{i}x_{i}\leq W&\\&x_{i}\in \mathbb {N} &(\forall i\in I)\end{array}}$

ここで、$x_{i}$ はナップサックへ入れる品物の個数を表している。

0-1 ナップサック問題

ナップサック問題において $x_{i}\in \mathbb {N}$ という制約を $x_{i}\in \{0,1\}$ と制限した問題を 0-1 ナップサック問題 という。元のナップサック問題では重量の合計がW以下であれば各品物はいくつでも入れることができたが、この問題の場合は1つまでである。

問題は次のように書かれる。

${\begin{array}{lll}\max &\sum _{i\in I}v_{i}x_{i}&\\\mathrm {s.t.} &\sum _{i\in I}w_{i}x_{i}\leq W&\\&x_{i}\in \{0,1\}&(\forall i\in I)\end{array}}$

解法について

この問題は、もしも全数探索を行えば「品物を選ぶ・選ばない」の2通りの選択肢を品物の個数分だけ試すことになり、その計算量は$O(2^{|I|})$になる。しかし、効率の良い貪欲法による解法が知られており，ここではその解法を示す。

この問題における漸化式は

$V(i,w)={\begin{cases}0&{\text{if }}i=0{\text{ or }}w=0\\V(i-1,w)&{\text{if }}w_{i}>w\\\max(V(i-1,w),V(i-1,w-w_{i})+v_{i})&{\text{otherwise}}\end{cases}}$

となる。ここで V(i, w) の値は重量の合計がｗ以下である場合に，添字がi以下の品物を使って実現できる価値の合計の最大値を表す。この式は

• 「1つも品物を選べない」あるいは「最大重量が $0$」であるときには、詰め込める品物がないので選ばれた品物の価値の合計を $0$ とする
• 品物 $i$ の重さが $w$ を超えている場合は、品物 $i$ は追加できないから、価値の合計は品物の添字の上限が1つ前までのものの価値の最大値になる
• 品物 $i$ の重さが $w$ を越えていない場合には、品物 $i$ を追加しない場合と追加をする場合の価値の最大値の両方のうちで、小さくない方の値にする

ということを表している。擬似コードは次の通り。価値の合計の最大値は V(|I|, W) として得られる。さらに選んだ品物の列挙をするにはコードの追加が要る。

array ${\textstyle V[0\ldots n,0\ldots W]}$;

$n\leftarrow |I|$

for $w\leftarrow 0$ to $W$ do　$V[0,w]\leftarrow 0$　end for

for $i\leftarrow 1$ to n do　$V[i,0]\leftarrow 0$　end for

for $i\leftarrow 1$ to n do

　 for $w\leftarrow 0$ to $W$ do

　　　 if $w_{i}>w$ then　$V[i,w]\leftarrow V[i-1,w]$

　　　　　　　　　else　$V[i,w]\leftarrow \max(V[i-1,w],V[i-1,w-w_{i}]+v_{i})$

　　　end if

　end for

end for

Groovy でトップダウンの動的計画法（メモ化再帰）を使ったコードは以下の通り。

@Memoized int m(int i, int j) {
    i == 0 ? 0 : Math.max(m(i - 1, j), c[i] <= j ? m(i - 1, j - c[i]) + p[i] : 0)
}

関連項目

• 計算複雑性理論
• 最適化問題
• 複雑性クラス - NP完全、NP困難
• ビンパッキング問題
• Merkle-Hellmanナップサック暗号

外部リンク

• MAXIMUM KNAPSACK
• Dynamic programming 0-1 Knapsack problem
• The Knapsack Problem