目次

動的計画法（ナップサック問題）

動的計画法とナップサック問題について解説します。

動的計画法とは

ナップサック問題

ナップサック問題は、価値と重さが決まっている複数の品物を容量が一定のナップサックに詰め込むとき、ナップサックに詰め込める品物の価値の和の最大値は何であるか？　という問題です。

具体的には、以下の図のようになります。ナップサックに書かれている「15kg」が容量で、周囲の品物（箱）に書かれている数字が価値と重さを表しています。

ナップサック

画像はWikipediaより改変（Dake, Keenan Pepper / CC BY-SA 2.5）

解法案

ナップサック問題についておおざっぱに方針を考えると、以下のような解法が思い浮かぶかもしれません。

全パターンを試せば、明らかに正しい答えを得ることができます。ただし、品物の数をnとすると計算量が\([O(2^n)]\)ほどあり、まともに計算できるのはnが25くらいまでのときのみです。

優先順位をつける方法なら、品物をソートして容量をオーバーしないようにしながら順に選んでいけるので、高速に計算することができます。

しかし実は、優先順位をつける方法ではどうやっても正しい解を得ることはできません。
上の図の例でいつくかの優先順位を使って最大値を求めたときに得られる解は、次のようになります。

全探索で得られる20が正しい答えですが、他のやり方ではそれよりも小さな値になっています。

実は、ナップサック問題はNP困難な問題であり、ソートなどを用いて効率的に解くことは不可能だと考えられています。

深さ優先探索による実装

効率よい方法を考える前に、まずは全探索での実装を考えてみましょう。 全探索の方法として深さ優先探索（再帰関数）を使うことにします。

以下の例では、nが品物の個数、Wがナップサックの容量、w[i]とv[i]がそれぞれi番目の品物（品物i）の重さと価値を示します。

再帰関数をどう作るのかはやや悩ましいのですが、現在の注目している品物の番号と、現時点でのナップサックの残り容量を関数の引数にしてみるとうまくいきます。 再帰関数をrec(i, j)とし、「品物i～n-1を重さjのナップサックに入れたときの価値の最大値」を返す関数を表すことにします。

rec(0, W)という関数呼び出しの動作を考えてみます。 このとき、品物0を入れるとすると、品物1以降の価値の最大値は「品物0が使えず、ナップサックの容量がw[0]だけ減ったときの価値の最大値」と考えることができます。 すると、品物0を入れたときの価値の最大値はv[0]+rec(1, W-w[0])と再帰の形で表せます。 同様に品物0を入れないとすると、ナップサックの容量は変化しないので最大値はrec(1, W)と表せます。 rec(0, W)全体の最大値はその2つの大きい方になります。

このような関数呼び出しをiが1,2,3…と繰り返していけば、最終的な答えが得られそうです。 iがn（品物の数）以上のときのrec(i, j)は明らかに0になる（使える品物が1つもない）ので、この再帰計算は無限ループにならず必ず終了します。

プログラムは次のようになります。

const int MAX_N = 25; // nの最大値

// 入力
int n, W;
int w[MAX_N], v[MAX_N];

// i番目以降の品物から重さの和がj以下なるように選んだときの、
// 取りうる価値の総和の最大値を返す関数
int rec(int i, int j) {
  int res;
  if (i == n) {
    // 品物がもう残っていないときは、価値の和の最大値は0で確定
    res = 0;
  } else if (j < w[i]) {
    // 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理
    // i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする
    res = rec(i + 1, j);
  } else {
    // 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ
    res = max(
        rec(i + 1, j),
        rec(i + 1, j - w[i]) + v[i]
    );
  }
  return res;
}

void solve() {
  // 0番目以降で容量W以下の場合の結果を表示する
  cout << rec(0, W) << endl;
}

メモ化再帰による実装

上記のコードをよく解析すると、rec(i, j)は再帰されているので指数回数分だけ呼び出されるが、iとjが同じであればrec(i, j)の結果は常に一定であることがわかります（使える品物と使える容量が一定なら価値の和の最大値も一定となるため）。

そのため、rec(i, j)の結果を配列に記憶しておけば、同じ計算をする手間が省けます。それを実装すると次のようになります。

const int MAX_N = 1000; // nの最大値
const int MAX_W = 5000; // Wの最大値

// 入力
int n, W;
int w[MAX_N], v[MAX_N];

// メモ化テーブル。
// dp[i][j]はi番目以降の品物から重さの和がj以下なるように選んだときの価値の和の最大値を表す。
// -1なら値が未決定であることを表す
int dp[MAX_N + 1][MAX_W + 1];

// i番目以降の品物から重さの和がj以下なるように選んだときの、
// 取りうる価値の総和の最大値を返す関数
int rec_dp(int i, int j) {
  if (dp[i][j] != -1) {
    // すでに調べたことがあるならその結果を再利用
    return dp[i][j];
  }
  int res;
  if (i == n) {
    // 品物がもう残っていないときは、価値の和の最大値は0で確定
    res = 0;
  } else if (j < w[i]) {
    // 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理
    res = rec_dp(i + 1, j);
  } else {
    // 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ
    res = max(
        rec_dp(i + 1, j),
        rec_dp(i + 1, j - w[i]) + v[i]
    );
  }
  // 結果をテーブルに記憶する
  return dp[i][j] = res;
}

void solve_dp() {
  memset(dp, -1, sizeof(dp)); // メモ化テーブルを-1で初期化　以下のforループと等価
//  for (int i = 0; i < MAX_N + 1; i++)
//    for (int j = 0; j < MAX_W + 1; j++)
//      dp[i][j] = -1;
  
  // 0番目以降で容量W以下の場合の結果を表示する
  cout << rec_dp(0, W) << endl;
}

単純な再帰関数に数行追加しただけですが、計算効率が大幅に向上しています。

メモ化をするとiとjの1つの組み合わせについて1回計算するだけで済むので、計算量はO(nW)になります。 単純な再帰では\([O(2^n)]\)だったので、Wが極端に大きくなければ圧倒的な効率の良さです。

一度計算した結果を再利用して計算効率を上げているので、この解法は動的計画法を用いた解法だと言えます。（厳密には上記のプログラムでやっていることはメモ化探索と呼ばれるもので、動的計画法とは区別されることがある。本質的には同じ）

漸化式を用いた実装

上記のメモ配列dp[i][j]の変化をよく観察すると、iが大きくjが小さい順（使える品物と容量が少ない順）にメモの値が確定していくことがわかります。

これを考慮すると、メモ配列の中身を次のような漸化式として表現することができます。

$$[ dp[n][j] = 0 \\ dp[i][j] = \begin{cases} dp[i+1][j] & (j < w[i])\\ max\{dp[i+1][j],\ dp[i+1][j-w[i]] + v[i]\} & (j \ge w[i]) \end{cases} ]$$

この漸化式を使ってdp[i][j]を順に求めていく操作をプログラムで実装すると、次のようになります。

const int MAX_N = 1000; // nの最大値
const int MAX_W = 5000; // Wの最大値

// 入力
int n, W;
int w[MAX_N], v[MAX_N];

// DPテーブル
// dp[i][j]はi番目以降の品物から重さの和がj以下なるように選んだときの価値の和の最大値を表す。
int dp[MAX_N + 1][MAX_W + 1];

void solve_dp2() {
  for (int j = 0; j <= W; j++) {
    dp[n][j] = 0;
  }
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j <= W; j++) {
      if (j < w[i])
        dp[i][j] = dp[i + 1][j];
      else
        dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
    }
  }
  cout << dp[0][W] << endl;
}

再帰がなくなり、単純なforループで実装できています。

この方法も（狭義の）動的計画法であり、計算量はO(nW)となります。

両者のやり方の比較

基本的には大差はありません。

メモ化再帰の利点

漸化式の利点

コード

追記：string.hのインクルード抜けを修正しました。

その他の動的計画法で解ける問題の一例

色々あります。講習会でもそのうち取り扱うかも。

演習

参考文献