ナップサック問題とは？意味をやさしく解説

ナップサック問題とは

ナップサック問題は、計算複雑性理論における重要な問題の一つで、与えられた制約の中で最適な組み合わせを見つけ出す問題です。具体的には、それぞれの品物に価値と重さが設定されており、ナップサック（袋）に入れられる重さの上限が決められている状況で、ナップサックに入れる品物の価値の合計を最大化することを目的とします。

この問題にはいくつかのバリエーションがあり、主なものとして、各品物を1つまでしか入れられない「0-1ナップサック問題」と、同じ品物を複数個入れてもよい「ナップサック問題」があります。

定義

品物の集合を \(I = \{1, 2, ..., N\}\) とし、各品物 \(i \in I\) の重さを \(w_i\)、価値を \(v_i\) とします。ナップサックに入れられる重さの上限を \(W\) とすると、ナップサック問題は以下のように定式化できます。

\[\max \sum_{i \in I} v_i x_i\]
\[\text{s.t.} \sum_{i \in I} w_i x_i \leq W\]
\[x_i \in \mathbb{N} \quad (\forall i \in I)\]

ここで、\(x_i\) は品物 \(i\) をナップサックに入れる個数を表します。

0-1 ナップサック問題

「0-1ナップサック問題」は、各品物を1つまでしか入れられないという制約を加えたものです。つまり、\(x_i\) は0または1の値しか取れません。この問題は以下のように定式化されます。

\[\max \sum_{i \in I} v_i x_i\]
\[\text{s.t.} \sum_{i \in I} w_i x_i \leq W\]
\[x_i \in \{0, 1\} \quad (\forall i \in I)\]

計算の複雑さ

ナップサック問題は、すべての品物の組み合わせを試す全数探索を行うと、品物の個数を\(n\)とした場合、計算量は\(O(2^n)\)となります。これは、品物の数が増えるにつれて計算時間が指数関数的に増加することを意味します。そのため、より効率的な解法が求められます。

動的計画法による解法

ナップサック問題は、動的計画法を用いて効率的に解くことができます。動的計画法では、部分問題を解きながら、その結果をテーブルに保存し、後で再利用することで、計算量を大幅に削減します。

以下は動的計画法による漸化式です。

\[V(i, w) = \begin{cases} 0 & \text{if } i = 0 \text{ or } w = 0 \\ V(i-1, w) & \text{if } w_i > w \\ \max(V(i-1, w), V(i-1, w-w_i) + v_i) & \text{otherwise} \end{cases}\]

ここで、\(V(i, w)\) は、重さの合計が\(w\)以下の場合に、品物\(i\)までを使って実現できる価値の合計の最大値を表します。

この漸化式に基づいた擬似コードは次のようになります。

array V[0...n, 0...W];
n ← |I|;

for w ← 0 to W do
V[0, w] ← 0;
end for
for i ← 1 to n do
V[i, 0] ← 0;
end for
for i ← 1 to n do
for w ← 0 to W do
if wi > w then
V[i, w] ← V[i-1, w];
else
V[i, w] ← max(V[i-1, w], V[i-1, w-wi] + vi);
end if
end for
end for

最終的に、\(V(|I|, W)\) が、ナップサックに入れることができる価値の合計の最大値となります。

実用的な解法

動的計画法以外にも、擬多項式時間アルゴリズムや、FPTAS（Fully Polynomial Time Approximation Scheme）などの解法が知られており、実用上は十分な精度で解を求めることができます。

外部リンク

もう一度検索

ナップサック問題