スマートフォン用の表示で見る

ナップサック問題

コンピュータ

ナップサック問題

なっぷさっくもんだい

計算複雑性理論における計算の難しさの議論の対象となる問題のひとつ。


容量 C のナップサックが一つと、n 個の品物(各々、価値 pi, 容積 ci)が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化する問題。NP困難であることが知られている。全ての品物について pi=ci が成り立つとき、部分和問題と等価であるため、この問題を含んでいる。