ナップサック問題
【英】:knapsack problem
重さがの物品をナップサックに詰めるとき, 重量制限 の下で価値 の総和が最大になるものを選ぶという次の整数計画問題.
目的関数 | 最大化 |
制約条件 | :非負整数 |
NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.
Weblioに収録されているすべての辞書からナップサック問題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からナップサック問題 を検索
- ナップサック問題のページへのリンク