ナップサック問題
ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（xi ∈ {0, 1}）や、同じ品物をいくつでも入れてよい場合（xi ∈ 0以上の整数）など、いくつかのバリエーションが存在する。
決定問題としてのナップサック問題は、「C, pi, ci のほかに価値の合計の目標 V が与えられたとき、容量 C 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方はあるか」を判定することである。 全ての品物について pi = ci が成り立つとき、部分和問題と等価であるため、ナップサック問題は部分和問題を一般化したものといえる。ナップサック問題は、（部分和問題もそうだが）NP困難と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全(NPかつNP困難)と呼ばれるクラスにも属する。
動的計画法を用いた擬多項式時間アルゴリズムや FPTAS の存在が知られているため、実用的には、ほぼ最適解を得られる。
Contents
定義
[math]I=\{1,2,\cdots,N\}[/math] を品物の集合とし、各品物 [math]i \in I[/math] の重みを[math]w_i[/math]、価値を [math]v_i[/math]、品物の最大容量を [math]W[/math] としたとき、次のようにあらわされるものをナップサック問題という。
- [math] \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} [/math]
ここで、[math]x_i[/math] はナップサックへ入れる品物の個数を表している。
0-1 ナップサック問題
ナップサック問題において [math]x_i \in \mathbb{N}[/math] という制約を [math]x_i \in \{0, 1\}[/math] と制限した問題を 0-1 ナップサック問題 という。元のナップサック問題では品物を容量さえ満たしていればいくつでもとることができたが、この問題では各品物を最大でも1つしかとることができない。
問題は次のように書かれる。
- [math] \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} [/math]
解法例
この問題は、全探索を行うと「品物を選ぶ・選ばない」の2通りの選択肢を品物の個数分の組み合わせを試すことになるため、[math]O(2^{|I|})[/math]かかってしまうが、より効率のいい貪欲法による解法が知られている。ここではその貪欲法を使った解法を示す。
この問題における漸化式は
- [math] V(i, w) = \begin{cases} 0 & \text{if } i = 0 \text{ or } w = 0 \\ V(i - 1, w) & \text{if } w_i \gt w \\ V(i - 1, w - w_i) + v_i & \text{otherwise} \end{cases} [/math]
となる。この式は
- 「選べる品物がない」あるいは「ナップサックの最大容量が [math]0[/math]」なときは詰め込める品物がないので選ばれた品物の総価値は [math]0[/math] とする
- 品物 [math]i[/math] を追加したときに、選択できる最大容量 [math]w[/math] を超てしまうときは [math]i[/math] を追加しないで総価値を1つ小さい問題のものとする
- 品物 [math]i[/math] を詰め込んでも選択できる最大容量 [math]w[/math] よりも大きくならないときは [math]i[/math] を追加する
ということを表している。 擬似コードは次の通り。
for [math]w \leftarrow 0[/math] to [math]W[/math] do [math]V[0, w] \leftarrow 0[/math] end for for [math]i \leftarrow 0[/math] to [math]|I|[/math] do [math]V[i, 0] \leftarrow 0[/math] end for for [math]i \leftarrow 1[/math] to [math]|I|[/math] do for [math]w \leftarrow 0[/math] to [math]W[/math] do if [math]w_i \leq w[/math] then [math]V[i, w] \leftarrow V[i - 1, w - w_i] + v_i[/math] else [math]V[i, w] \leftarrow V[i - 1, w][/math] 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)
}