【なっぷさっくもんだい】
ナップサック問題 とは？
💡 リュックに何を詰める？限られたスペースで最大の価値を狙う頭脳パズル
📌 このページのポイント
ひよこ ナップサック問題って、リュックに荷物を詰める話なの？
ペンギン先生 そうそう。リュックに入る重さの上限があって、その中で「持っていく物の価値の合計」を最大にしたいっていう問題だよ。たとえば10kgまで入るリュックに、3kgで5万円のカメラと7kgで8万円のノートPCと6kgで6万円のタブレットがあったら、どれを入れる？っていうパズルだね
ひよこ 全部入れればいいんじゃ…あ、重さオーバーしちゃうのか！
ペンギン先生 そう、全部で16kgになるから入りきらない。カメラ＋ノートPCなら10kgで13万円、カメラ＋タブレットなら9kgで11万円。こうやって組み合わせを考えて最大価値を見つけるのがナップサック問題だよ
ひよこ 品物が増えたら大変そう…全部の組み合わせを調べるの？
ペンギン先生 品物がn個あると組み合わせは2のn乗通りになるから、30個でも約10億通り。だから「動的計画法」っていうテクニックで効率よく解くんだ。一度計算した結果を表に記録しながら進めることで、無駄な再計算を省けるんだよ
ひよこ 実際のITでも使われるの？
ひよこ じゃあ完璧な答えをパッと出せるアルゴリズムってあるの？
まとめ：ざっくりこれだけ覚えればOK！
「ナップサック問題」って出てきたら「限られた容量で最大の価値を詰め込む最適化パズル」と思えればだいたいOK！
📖 おまけ：英語の意味
「Knapsack Problem」 ＝ ナップサック問題
💬 Knapsackはドイツ語由来の「背負い袋」のこと。旅行者がリュックに何を入れるか悩む場面がそのまま問題名になったんだよ