ナップサック問題
ナップサック問題（ナップサックもんだい、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 の存在が知られているため、実用的には、ほぼ最適解を得られる。
0-1 ナップサック問題
各種類の品物はそれぞれ1つずつしかない場合を 0-1 ナップサック問題 という。動的計画法で厳密解が求まる。
問題文は数式では以下のように表現される。
- <math>\sum_{i=1}^n c_i x_i \le C, \quad x_i \in \{0,1\}</math> の元で <math>\sum_{i=1}^n p_i x_i</math> の最大値を求める
m[i, j] を i 番目までの品物を使い、容量 j での最大値とする。m[n, C] が求める答え。
m[n, C] = 下記2つの大きい方
xn = 0 の場合：つまり品物 n を積まないか、もしくは、品物 n の cn が大きすぎて積めない場合
m[n - 1, C]
xn = 1 の場合：つまり品物 n を積む場合
m[n - 1, C - cn] + pn
これをボトムアップの動的計画法にした擬似コードは以下の通り。
for (j from 0 to C) {
m[0, j] = 0
}
for (i from 1 to n) {
for (j from 0 to C) {
if (c[i] <= j) {
m[i, j] = max(m[i - 1, j], m[i - 1, j - c[i]] + p[i])
} else {
m[i, j] = m[i - 1, j]
}
}
}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)
}関連項目
外部リンク
