ナップザック‐もんだい【ナップザック問題】
ナップサック問題
【英】:knapsack problem
重さがの物品をナップサックに詰めるとき, 重量制限 の下で価値 の総和が最大になるものを選ぶという次の整数計画問題.
目的関数 | 最大化 |
制約条件 | :非負整数 |
NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.
ナップサック問題
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/05/07 02:08 UTC 版)
ナップサック問題(ナップサックもんだい、Knapsack problem)は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物(各々、価値 vi、重量 wi)が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合(xi ∊ {0, 1})や、同じ品物をいくつでも入れてよい場合(xi は0以上の整数)など、いくつかのバリエーションが存在する。
- 1 ナップサック問題とは
- 2 ナップサック問題の概要
- 3 関連項目
- ナップサック問題のページへのリンク