ナップサック問題

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