ナップザック問題

デジタル大辞泉

ナップザック‐もんだい【ナップザック問題】

読み方：なっぷざっくもんだい

ある容量のナップザックの中に、大きさや価格が異なる何種類もの品物を詰めるとき、どの品物を選べば価格や重量を最大化できるかを問う問題。直接計算すると膨大な時間がかかる組み合わせ爆発の一例。動的計画法により、実用的な解を得ることができる。

OR事典

ナップザック問題

読み方：なっぷざっくもんだい
【英】：knapsack problem

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

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

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

ウィキペディア

ナップサック問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/05/07 02:08 UTC 版)

ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物（各々、価値 v_i、重量 w_i）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（x_i ∊ {0, 1}）や、同じ品物をいくつでも入れてよい場合（x_i は0以上の整数）など、いくつかのバリエーションが存在する。