読み方：ナップサックもんだい

ナップサック問題【knapsack problem】

ナップサック問題とは？

コンピュータ科学で扱われる問題の一つで、容量に限りのある袋に対して、複数の荷物の中からどれを選んで詰めれば価値の合計を最大化できるかを求めるもの。組み合わせ最適化問題の代表的な問題として広く知られている。

それぞれ重さと価値が異なる複数の品物があり、決められた重さまでしか入らない袋（ナップザック）に品物を選んで詰めるとき、袋に入れた品物の価値の合計をできるだけ大きくしたい、という問題である。旅行の荷造りや買い物など、日常生活にもよくある状況設定である。

一見シンプルに見える問題だが、品物の数が増えると一気に難しくなる。すべての組み合わせを虱潰しに試そうとすると、n個の品物について2ⁿ通りの候補を調べる必要がある。品物が30個あれば10億通りを超えるため、単純な全探索では現実的な時間内に解を求められなくなる。

この問題はコンピュータ科学上の概念である「NP困難」に分類されており、多項式時間で必ず最適解を求めるアルゴリズムは現在のところ知られていない。ただし「動的計画法」と呼ばれる手法を使えば、重さの上限と品物の数が小さい範囲においては効率的に最適解を求めることができる。動的計画法では、小さな部分問題の答えを順番に記録・再利用しながら全体の解を構築していく。

実用上は最適解を厳密に求めるのではなく、近似解で妥協する手法も多く用いられる。遺伝的アルゴリズムや貪欲法などのヒューリスティクス（経験則）がその例であり、厳密解よりも短い時間でそれに近い答えを得ることができる。物流における積載計画、投資ポートフォリオの選定、タスクのスケジューリングなど、現実の意思決定問題にも広く応用されている。