ナップサック問題

提供: ORWiki
2007年7月13日 (金) 13:43時点における211.9.146.171 (トーク)による版
ナビゲーションに移動 検索に移動

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

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

目的関数  最大化
制約条件  :非負整数

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