【ナップサック問題】
ナップサック問題は、複数の品物それぞれに価値と重さが与えられたとき、ある重量以下の容量を持つナップサックに品物を詰め込んで、価値の合計を最大化するように選ぶ問題です。ナップサック問題は組み合わせ最適化問題の一種であり、コンピュータサイエンスや数学、経済学、オペレーションズリサーチなどの分野で応用されています。
例えば、容量が10kgのナップサックがあり、以下の3つの品物があります。それぞれの品物の重さと価値は以下の通りです。
| 品物 | 重さ(kg) | 価値(円) |
|---|---|---|
| 1 | 3 | 700 |
| 2 | 4 | 900 |
| 3 | 5 | 1200 |
この場合、ナップサックに品物1と品物3を詰め込むことで、価値の合計を最大化することができます。重さは3kg+5kg=8kgで、容量の制限である10kgを超えていません。
ナップサック問題には、以下のようなバリエーションがあります。
・0/1ナップサック問題：各品物を選ぶか選ばないかの2択であり、一度選んだ品物を後から外すことはできない。
・部分的ナップサック問題：各品物を無限に分割できるものとし、任意の割合で詰め込むことができる。
・多次元ナップサック問題：各品物に対して複数の重量や価値が与えられるものとし、それぞれの制約を満たしつつ、複数の制約の中で最大化する。
ナップサック問題は、全探索による解法が存在しますが、品物の数や重さの範囲が大きい場合には計算時間が膨大になるため、動的計画法や貪欲法などの高速な解法が開発されています。また、ナップサック問題はNP困難とされており、完全な解法を求めることは困難であるとされています。