ナップサック問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
ナップサック問題

ナップサック問題(ナップサックもんだい、Knapsack problem)は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、「容量 Cナップサックが一つと、n 個の品物(各々、価値 pi, 容積 ci)が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。同じ種類の品物を一つまでしか入れられない場合(n = 1)や、同じ品物をいくつでも入れてよい場合(n = 無限大)など、いくつかのバリエーションが存在する。

決定問題としてのナップサック問題は、「C, pi, ci のほかに価値の合計の目標 V が与えられたとき、容量 C 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方はあるか」を判定することである。 全ての品物について pi = ci が成り立つとき、部分和問題と等価であるため、ナップサック問題は部分和問題を一般化したものといえる。ナップサック問題は、(部分和問題もそうだが)NP困難と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全(NPかつNP困難)と呼ばれるクラスにも属する。

動的計画法を用いた擬多項式時間アルゴリズムFPTAS の存在が知られているため、実用的には、ほぼ最適解を得られる。

上記で n = 1 、つまり、品物はそれぞれ1つずつしかない場合を 0-1 ナップサック問題 という。動的計画法で厳密解が求まる。

関連項目[編集]

外部リンク[編集]