ナップサック問題

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

重さが$a_{i}\,$の物品構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\,} をナップサックに詰めるとき, 重量制限 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b\,} の下で価値 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c_i\,} の総和が最大になるものを選ぶという次の整数計画問題.

目的関数	構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sum_{i=1}^{n} c_{i}x_{i} \to \,} 最大化
制約条件	構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sum_{i=1}^{n} a_{i}x_{i} \leq b,x_i\,} ：非負整数

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