「ナップサック問題」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
("ナップサック問題" を保護しました。 [edit=sysop:move=sysop])
 
7行目: 7行目:
 
</table>
 
</table>
 
NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.
 
NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.
 +
 +
[[Category:組合せ最適化|なっぷさっくもんだい]]
 +
 +
[[category:近似・知能・感覚的手法|なっぷさっくもんだい]]
 +
 +
[[Category:グラフ・ネットワーク|なっぷさっくもんだい]]

2008年11月13日 (木) 13:22時点における最新版

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

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

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

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