ナップザック問題（個数制限あり、なし）を動的計画法で解くために理解する

ナップザック問題とは、「n 種類の品物（各々、価値 v_i、重量 w_i）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」（Wikipedia）という問題です。

ナップザック問題（各1個）

ナップザック問題の基本パターンとして、品物が1個ずつの場合がよく説明される。例えば、n=3の場合で考えてみる。品物を〇、□、△としてそれぞれの価値、重さを



とし、ナップザックに入れられる重さの上限を10として、最も価値が高くなるように品物を選ぶ。

まず、解を全探索（それぞれの品物を選ぶ・選ばないをbitで表すとbit全探索）で求めると、



と解13が得られる。このn=3の場合は、2³-1通り（どれも選ばないを除くため）なので、全探索でも解が得られる。しかし、n=20になると、2¹⁰-1=048575通りと計算量が大幅に増加してしまう。

DP（動的計画法）

これを動的計画法で解くと、このようになる。



この表は、重さ1～10の各重さごとに、価値が最大になる品物の選び方を決めたものである。

• 重さの上限が1、2のときは、どの品物も選ぶことができない
• 重さの上限が3のとき、品物□のみ選ぶことができるので、品物□を選び、価値は5となる
• 重さの上限が4のとき、品物□の代わりに品物〇を選ぶと価値が7で最大となる
• 重さの上限が5、6のとき、重さの上限が4のときの状態を維持する
• 重さの上限が7のとき、品物□を加えることができ、価値は12となる
• 重さの上限が8のとき、重さの上限が7の状態を維持する
• 重さの上限が9のとき、品物□の代わりに品物△を選ぶと、価値は13となる
• 重さの上限が10のとき、重さの上限が9の状態を維持する

重さの上限が3から4になるときを見てみる。重さの上限が3のときは品物□が選ばれているが、上限が4になると品物〇と△を選ぶことができるかどうかを調べる。品物〇を選ぶには、品物〇の重さ4だけ重さの和が小さい状態（つまり重さの上限が0の状態＝品物□を選んでいない）に対して品物〇を追加した状態を考える。この状態の価値は品物〇の価値7となる。品物△は重さが7なので選ぶことはできない。品物〇を選ばない場合は、重さの上限が3のとき維持するため、品物〇を選ぶことで価値が増える。価値が大きい状態を選択するので、品物□の代わりに品物〇を選ぶ。

このような手順で、重さの上限を1から10まで増やしていきながら、価値の最大値を更新していく。そこで、下のような表を作る。



どの品物も選ばない状態を初期値として、表の上から下に品物を順番に調べていく。各品物について、重さの上限0～10までとして品物を選ぶ・選ばないで価値が最大になる方を選んでいく。表の各マスは、品物をi、重さをjとしてdp[i][j]と表し、マスの中には価値の最大値を書いていく。

品物〇を選ぶ・選ばないを調べていくには、初期状態（i=0）に対して、品物〇の重さだけ小さい重さのときの価値の最大値＋品物〇の価値と、品物〇を選ばないときの価値の大きい方をそのマスに書いていく。

品物□を選ぶ・選ばないを調べていくときは、品物〇について調べた状態に対して、品物□の重さだけ小さい重さのときの価値の最大値＋品物□の価値と、品物□を選ばない（品物〇を調べた状態）ときの価値の大きい方をそのマスに書いていく。品物△についても、同じように調べていく。

品物〇について、重さの上限が4のときを式で表すと、

• 品物〇を選ぶ場合：dp[1][4] = dp[0][0] + 7
• 品物〇を選ばない場合：dp[1][4] = d[0][4]

となり、大きい方の値をdp[1][4]とする。品物〇、品物□、品物△についてそれぞれ調べていくと、

品物〇について調べた状態



品物□について調べた状態



品物△について調べた状態

と表のすべてのマスを埋めることができ、品物3つついて、重さの和が10以下のときの価値の最大値がdp[3][10]に得られている。この表をすべて埋めるのには、3×10=30（i=0は初期値でi=1～3を計算）の計算量となる。

n=3の場合で見ると、全探索の方が計算量が少ないが、n=20になると20×10=200回となり、動的計画法の方がはるかに少ない計算量で解を得ることができる。

実装例（C++）

3つの品物について、各品物の価値、重さが一行ずつ与えられる。

7 4
5 3
6 5

各行の価値、重さをvectorに読み込んで、ナップザック問題を解いていく。

int main() {
  int n = 3, m = 10;                    /* 3 items, weight <= 10 */
  vector<int> v(n), w(n);               /* v: value, w: weight */
  for (int i = 0; i < n; i++)
    cin >> v[i] >> w[i];
}

重さ1～mで価値が最大になるように、品物1～nを選ぶ・選ばないを決めていく。

int main() {
  int n = 3, m = 10;                    /* 3 items, weight <= 10 */
  vector<int> v(n), w(n), c(n);         /* v: value, w: weight, c: count */
  for (int i = 0; i < n; i++)
    cin >> v[i] >> w[i] >> c[i];

  vector<vector<int>> dp(n+1, vector<int> (m+1, 0)); /* vector table*/
  for (int i = 0; i < n; i++) {
  	for (int j = 1; j < m+1; j++) {
      if (j < w[i])
	      dp[i+1][j] = dp[i][j];
      else
	      dp[i+1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j]);
    }
  }
  cout << dp[n][m] << endl;
}

ナップザック問題（個数あり）

各品物に対して、複数個選べる場合を考える。例として□のみ3個を上限として選べる場合を考える。



品物□について、個数1～3で価値が最大になる場合を調べると、

  vector<vector<int>> dp(n+1, vector<int> (m+1, 0)); /* vector table */
  for (int i = 0; i < n; i++) {
    for (int j = 1; j < m+1; j++) {
      for (int k = 1; k <= c[i]; k++) { /* check item numbers for c[i] */
        if (j < w[i] * k)
          dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
        else
          dp[i+1][j] = max({dp[i][j - w[i]*k] + v[i]*k, dp[i+1][j], dp[i][j]});
        }
    }
  }

のようなコードが書ける。

これをdp表（上のコードと同一ではないが、個数1～3について調べる部分をdp表上に展開した形）にしてみると、



とできるが、ここで3個を選ぶというのは、1個と2個の両方を選ぶのと同じなので、3個の場合は不要で



とできる。

これは、数を2進表記するのと同じで、例えば7以下の数は、1と2と4の組み合わせで表現できる。ただし、例えば10の場合、1と2と4と8の組み合わせで表現しようとすると、1+2+4+8=16となり上限の10を超えてしまうことに注意が必要である。そこで、組み合わせの最大値が上限の10になるように、1+2+4+3とする。



このようにすると、例えば10個の個数を調べるのに、4つの組み合わせで済むことになる。

数を2の累乗数に分解する（x=2⁰+2¹+...+2ⁿ+m）には、

vector<int> decomp(int x) {             /* decomposition */
  vector<int> v;                        /* array size undeclared */
  int p = 1;
  while (x > 0) {
    v.push_back(min(p, x));             /* append 2^x or residual */
    x -= min(p, x);
    p *= 2;
  }
  return v;
}

とすることで、配列 [2⁰, 2¹, ... , 2ⁿ, m] が生成される。これを使って、

int main() {
  int n = 3, m = 10;                    /* 3 items, weight <= 10 */
  vector<int> v, w;                     /* array size undeclared */
  for (int i = 0; i < n; i++) {
    int vi, wi, ci;
    cin >> vi >> wi >> ci;
    vector<int> d = decomp(ci);         /* decomposition */
    for (int x : d) {                   /* item of 2^? */
      v.push_back(v * x);
      w.push_back(w * x);
    }
  }
  int nn = (int)v.size();

  vector<vector<int>> dp(nn+1, vector<int> (m+1, 0)); /* dp table */
  for (int i = 0; i < nn; i++) {
    for (int j = 1; j < m+1; j++) {
      if (j < w[i])
        dp[i+1][j] = dp[i][j];
      else
        dp[i+1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j]);
    }
  }
  cout << dp[nn][m] << endl;
}

ナップザック問題（個数制限なし）

各品物に個数制限がなく、何個でも選ぶことができる問題の場合を考える。

この場合、各品物の個数の上限＝重さの上限を超えない範囲の最大の個数、となる。つまり、

    int ci = m / wi;

と個数の上限の計算式を挿入して、

  for (int i = 0; i < n; i++) {
    int vi, wi;
    cin >> vi >> wi;                    /* no limit for number of item */
    int ci = m / wi;                    /* upper limit of number of item */
    vector<int> tmp = decomp(ci);       /* decomposition */
    for (int x : tmp) {                 /* item of 2^? */
      v.push_back(v * x);
      w.push_back(w * x);
    }
  }

とすればいい。