ナップサック問題

デジタル大辞泉

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

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

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

OR事典

ナップサック問題

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

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

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

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

「OR事典」の他の用語

グラフ･ネットワーク：	ダイクストラ法  ダルメジ・メンデルゾーン分解  デルタマトロイド  ナップサック問題  ネットワーク  ネットワークフロー問題  フェンシェル型双対定理
組合せ最適化：	グラフ彩色問題  グレブナー基底  データ構造  ナップサック問題  ネットワークフロー問題  ハッシュ表  パーフェクトグラフ
近似・知能・感覚的手法：	タブー探索  デンプスター・シェファーの証拠理論  データマイニング  ナップサック問題  ニューラルネットワーク  ニューラルネットワークによる学習  ファジィランダム変数

ウィキペディア

ナップサック問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/14 06:02 UTC 版)

ナップサック問題

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

決定問題としてのナップサック問題は、「W, v_i, w_i のほかに価値の合計の目標 V が与えられたとき、重量の合計が W 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方が存在するか」を判定することである。 全ての品物について v_i = w_i である場合は、部分和問題と等価であるため、ナップサック問題は部分和問題の一般化である。ナップサック問題は、（部分和問題もそうであるが）NP困難と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全（NPかつNP困難）と呼ばれるクラスにも属する。

解法として、動的計画法を用いた擬多項式時間アルゴリズムや FPTAS の存在が知られており、実用的にはほぼ最適な解が得られる。

定義

$I=\{1,2,\cdots ,N\}$