ナップサック問題
ナップサック問題(ナップサックもんだい、Knapsack problem)は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物(各々、価値 vi、重量 wi)が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合(xi ∊ {0, 1})や、同じ品物をいくつでも入れてよい場合(xi は0以上の整数)など、いくつかのバリエーションが存在する。
決定問題としてのナップサック問題は、「W, vi, wi のほかに価値の合計の目標 V が与えられたとき、重量の合計が W 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方が存在するか」を判定することである。 全ての品物について vi = wi である場合は、部分和問題と等価であるため、ナップサック問題は部分和問題の一般化である。ナップサック問題は、(部分和問題もそうであるが)NP困難と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全(NPかつNP困難)と呼ばれるクラスにも属する。
解法として、動的計画法を用いた擬多項式時間アルゴリズムや FPTAS の存在が知られており、実用的にはほぼ最適な解が得られる。
品物 i {\displaystyle i} の重さが w {\displaystyle w} を超えている場合は、品物 i {\displaystyle i} は追加できないから、価値の合計は品物の添字の上限が1つ前までのものの価値の最大値になる
品物 i {\displaystyle i} の重さが w {\displaystyle w} を越えていない場合には、品物 i {\displaystyle i} を追加しない場合と追加をする場合の価値の最大値の両方のうちで、小さくない方の値にする
ということを表している。擬似コードは次の通り。価値の合計の最大値は V(|I|, W) として得られる。さらに選んだ品物の列挙をするにはコードの追加が要る。
array V [ 0 ... n , 0 ... W ] {\textstyle V[0\ldots n,0\ldots W]} ;
n ← | I | {\displaystyle n\leftarrow |I|}
for w ← 0 {\displaystyle w\leftarrow 0} to W {\displaystyle W} do V [ 0 , w ] ← 0 {\displaystyle V[0,w]\leftarrow 0} end for