ナップサック問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ナップサック問題（なっぷさっくもんだい）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、「容量 C のナップサックが一つと、n 個の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。同じ種類の品物を一つまでしか入れられない場合や、同じ品物をいくつでも入れてよい場合など、いくつかのバリエーションが存在する。
決定問題としてのナップサック問題は、「C, pi, ci のほかに価値の合計の目標 V が与えられたとき、容量 C 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方はあるか」を判定することである。 全ての品物について pi = ci が成り立つとき、部分和問題と等価であるため、ナップサック問題は部分和問題を一般化したものといえる。ナップサック問題は、（部分和問題もそうだが）NP完全であることが知られている。
動的計画法を用いた擬多項式時間アルゴリズムや FPTAS の存在が知られているため、実用的には、ほぼ最適解を得ることができる。
[編集] 関連項目
[編集] 外部リンク
