Hatena Blog Tags

ナップサック問題

(コンピュータ)
なっぷさっくもんだい

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


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

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

ネットで話題

もっと見る

関連ブログ