ナップザック問題

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

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

目的関数	構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sum _{i=1}^{n}c_{i}x_{i}\to \,} 最大化
制約条件	構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sum _{i=1}^{n}a_{i}x_{i}\leq b,x_{i}\,} ：非負整数

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