ナップザック問題

【なっぷざっくもんだい (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困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.