ナップザック問題

デジタル大辞泉

ナップザック‐もんだい【ナップザック問題】

読み方：なっぷざっくもんだい

ある容量のナップザックの中に、大きさや価格が異なる何種類もの品物を詰めるとき、どの品物を選べば価格や重量を最大化できるかを問う問題。直接計算すると膨大な時間がかかる組み合わせ爆発の一例。動的計画法により、実用的な解を得ることができる。