ナップサック問題

【なっぷさっくもんだい (knapsack problem)】

重さが$a_{i}\,$の物品$i\,$をナップサックに詰めるとき, 重量制限 $b\,$ の下で価値 $c_{i}\,$ の総和が最大になるものを選ぶという次の整数計画問題.

目的関数	$\sum _{i=1}^{n}c_{i}x_{i}\to \,$最大化
制約条件	$\sum _{i=1}^{n}a_{i}x_{i}\leq b,x_{i}\,$：非負整数

NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.