ナップサック問題

ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、 種類の品物（各々、価値 、重量 ）が与えられたとき、重量の合計が を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（}）や、同じ品物をいくつでも入れてよい場合（ は0以上の整数）など、いくつかのバリエーションが存在する。
決定問題としてのナップサック問題は、「 のほかに価値の合計の目標 が与えられたとき、重量の合計が 以内でナップサック内の品物の価値の合計が 以上になるような品物の選び方が存在するか」を判定することである。
全ての品物について である場合は、部分和問題と等価であるため、ナップサック問題は部分和問題の一般化である。ナップサック問題は、（部分和問題もそうであるが）NP困難と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全(NPかつNP困難)と呼ばれるクラスにも属する。
解法として、動的計画法を用いた擬多項式時間アルゴリズムや FPTAS の存在が知られており、実用的にはほぼ最適な解が得られる。
定義.
formula_1 を品物の集合とし、各品物 formula_2 の重みをformula_3、価値を formula_4、品物の重量の合計の上限を formula_5 とするとき、次のようにあらわされるものをナップサック問題という。
ここで、formula_7 はナップサックへ入れる品物の個数を表している。
0-1 ナップサック問題.
ナップサック問題において formula_8 という制約を formula_9 と制限した問題を 0-1 ナップサック問題 という。元のナップサック問題では重量の合計がW以下であれば各品物はいくつでも入れることができたが、この問題の場合は1つまでである。
問題は次のように書かれる。
解法について.
この問題は、もしも全数探索を行えば「品物を選ぶ・選ばない」の2通りの選択肢を品物の個数分だけ試すことになり、その計算量はformula_11になる。しかし、効率の良い貪欲法による解法が知られており，ここではその解法を示す。
この問題における漸化式は
となる。ここで の値は重量の合計がｗ以下である場合に，添字がi以下の品物を使って実現できる価値の合計の最大値を表す。この式は
ということを表している。擬似コードは次の通り。価値の合計の最大値は として得られる。さらに選んだ品物の列挙をするにはコードの追加が要る。
array formula_21;
formula_22
for formula_23 to formula_5 do　formula_25　end for
for formula_26 to n do　formula_27　end for
for formula_26 to n do 
　 for formula_23 to formula_5 do 
　　　 if formula_31 then　formula_32 
　　　　　　　　　else　formula_33 
　　　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)