定義
$I={1,2,…,N}$を品物の集合.
各品物$i \in I$の重みを$w_i$
価値を$v_i$
品物の重量の合計の上限を$W$とするとき
次のようにあらわされるものをナップサック問題という。
$$
max ∑{i \in I}v_iw_i\ s.t. ∑{i \in I}v_iw_i\le W\
x\in \mathbb{N}(\forall \in I)
$$
ここで、$x_i$はナップサックへ入れる品物の個数を表している。
解法
この問題は、もしも全数探索を行えば「品物を選ぶ・選ばない」の2通りの選択肢を品物の個数分だけ試すことになり、その計算量は$O(2^{|I|})$になる。しかし、効率の良い貪欲法による解法が知られており，ここではその解法を示す。この問題における漸化式は
$$
V(i,w)
=\begin{cases}
{0\quad if\,i= 0\,or\,w = 0}\
{V(i-1,w)\quad if\,w_i>w}\
{max(V(i-1),V(i-1,w-w_i)+v_i)\quad otherwise}
\end{cases}
$$
となる。ここで $V(i, w)$ の値は重量の合計が$w$以下である場合に，添字が$i$以下の品物を使って実現できる価値の合計の最大値を表す。この式は
- 「1つも品物を選べない」あるいは「最大重量が ${\displaystyle 0}{\displaystyle 0}$」であるときには、詰め込める品物がないので選ばれた品物の価値の合計を ${\displaystyle 0}{\displaystyle 0}$ とする
- 品物 ${\displaystyle i}$ の重さが ${\displaystyle w}$ を超えている場合は、品物 ${\displaystyle i}$ は追加できないから、価値の合計は品物の添字の上限が1つ前までのものの価値の最大値になる
- 品物 ${\displaystyle i}$ の重さが ${\displaystyle w}$ を越えていない場合には、品物 ${\displaystyle i}$ を追加しない場合と追加をする場合の価値の最大値の両方のうちで、小さくない方の値にする。
ということを表している。擬似コードは次の通り。価値の合計の最大値は V(|I|, W) として得られる。さらに選んだ品物の列挙をするにはコードの追加が要る。