ナップサック問題の動的計画法の仕組みや実装が全然わからんという方向けに、シンプルな解説を試みる記事です。
※ここでは重量や価値を整数として扱います
ナップサック問題とは
N個の品物には重量と価値が定められていて、ナップサックには入れられる最大重量Mが定められています。
N個の品物のうちいくつ品物を入れてもいいときに、ナップサックに入る最大重量Mを超えないように、入れた品物の価値の合計を最大化しようというのがナップサック問題でした。
この問題を解くときに総当たりよりも計算量が少なくて済むよいアルゴリズムが動的計画法でした。
動的計画法によるナップサック問題の解き方
動的計画法によるナップサック問題の解き方では、「i -1番目の品物までの最適解」を用いて「i番目の商品を入れるか入れないか」を考えます。
用意するもの
※ここでは価値や重量などはすべて整数です。
※配列の添字風の表記を用います。
品物の重量と価値は次のように表記します。
- i番目の品物の価値は「
品物[i-1].value」 - i番目の品物の重量は「
品物[i-1].weight」
そして、動的計画法のために表をつくります。
N個の品物と最大重量がMのナップサックがあるときは、
N+1行×M+1列の表 table[N+1][M+1]をつくります。
この表は、例えばtable[i][j]の値は、「品物[0]から品物[i-1]まで考慮して重量jまで許容したときの最大化された価値」になります。
つまり、全てのtable[i][j]の値は部分的な最適解です。
表を用いて最適解を計算する
結局、次のような式を用いて表の左上から計算していくことで、一番右下の値が全体の最適解になります。
\text{table}[i -1][j] \\
\text{table}[i -1][j ~- 品物[i -1].\text{weight}] + 品物[i -1].\text{value}
\end{cases}\]
つまり、table[i][j]の値は、
品物[i-1]を入れないときの最適解table[i-1][j]と、
品物[i-1]が入る場合の最適解table[i−1][j −品物[i−1].weight] + 品物[i -1].value
を比較したときの大きい方とすることで部分的な最適解になります。
※table[i−1][j −品物[i−1].weight]は、品物[i-1]がちょうど入れられるときの最適解です。プログラムにするときはj −品物[i−1].weightの値に注意が必要です。
これを左上から計算していくと、
まず0行目は品物を1つも入れることができないので、いくら最大重量jを大きくしても価値は0です。つまりすべての列の値は0です。
1行目は品物[0]を入れることができるので、品物[0].weight以上の値のj行については、table[1][j]の値は品物[0].valueになります。
2行目からは先の式の通り、品物[i-1]を入れるかどうかを1つ前の行の結果を参照しながら決めて、部分的最適解を埋めていきます。
計算量はどうなるのか
品物の数Nと最大重量Mを用いれば\(\mathcal{O}(NM)\)となって、NとMのどちらか大きい方だけに置き換えても2乗で押さえられそうです。
しかし、この動的計画法は擬多項式時間と呼ばれており、例えばMの桁数をmとおくと指数関数時間になってしまいます。
そのため、NやMが大きすぎると実用的でなくなります。
