2次元の動的計画法まとめ ナップザック問題編

動的計画法を用いて解くことができる問題のうち、ナップザック問題とその亜種問題の解法を自分用にまとめる。

基本のナップザック問題

問題

重さと価値がそれぞれ$w_i$, $v_i$であるような$N$個の商品がある$(1 \leq i \leq N)$。これらの商品の中から、重さの総和が$W$を超えないように選んだときの、価値の総和の最大値を求めなさい。

DPテーブル

DPテーブルの定義

$dp[i][j]$：$i$番目の商品まで選択対象に含めたとき、重さが$j$以下になるようにいくつかの商品を選んだときの、価値の総和の最大値。ただし、$0 \leq i \leq N, 0 \leq j \leq W$。

初期条件

重さが0ならば、$i$番目までの商品を1つも選んでいないことになるので、価値の総和も0になる。
また、$i = 0$のとき、選べる商品が1つもないので、価値の総和は0になる。

$$\begin{cases} dp[i][0] = 0 \quad (0 \leq i \leq N) \\ dp[0][j] = 0 \quad (0 \leq j \leq W) \end{cases}$$

漸化式

$i$番目$(1 \leq i \leq N)$までの商品を選択対象に含めたとき、

1. $i$番目の商品を選ばない
2. $i$番目の商品を(選べるならば)選ぶ

の2通りが考えられる。

$i$番目の商品を選ばなかった場合、価値の総和の値は、$i - 1$番目までの商品を選択対象に含めたときの値と等しくなる。

$i$番目の商品を選ぶ場合、$i - 1$番目までの商品を選択対象に含めた時点で、重さの総和を$j - w_i$にできる組み合わせがあるならば、$i$番目の商品を選ぶことによって、重さの総和をちょうど$j$にできる。このときの価値の総和は、$dp[i - 1][j - w_i]$に$i$番目の商品の価値$v_i$を加えたものになる。これと、$i$番目の商品を選ばなかったときの価値の総和のうち大きい方を取り、$dp[i][j]$に代入すればよい。

漸化式は以下のようになる。1段目が$i$番目の商品を選ばなかった場合で、2段目が$i$番目の商品を選んだ場合である。

$$dp[i][j] = \begin{cases} dp[i - 1][j] \\ \max(dp[i - 1][j], dp[i - 1][j - w_i] + v_i) \quad (j - w_i \geq 0) \end{cases} \quad (1 \leq i \leq N, 1 \leq j \leq W)$$

出力

$dp[N][W]$の値を出力すればよい。

例題と解答例

例題

• AtCoder Educational DP Contest D - Knapsack1
• アルゴ式 ナップザック問題

解答例

AtCoder Educational DP Contest D - Knapsack1のC++解答例のソースコードを以下に示す。

D - Knapsack1

#include <iostream>
#include <vector>

int main() {
  int64_t N, W;
  std::cin >> N >> W;
  // DPテーブルに合わせて、入力を受け取る配列は1-indexedにする
  // もちろん0-indexedでも全く問題なく解けるけど、漸化式がややこしく
  // なるので1-indexedにする
  std::vector<int64_t> w(N + 1);
  std::vector<int64_t> v(N + 1);
  for (int64_t i = 1; i <= N; i++) {
    std::cin >> w.at(i) >> v.at(i);
  }

  // DPテーブル
  std::vector<std::vector<int64_t>> dp(N + 1, std::vector<int64_t>(W + 1, 0));

  for (int64_t i = 1; i <= N; i++) {
    for (int64_t j = 1; j <= W; j++) {
      // i番目の要素を選ばない場合
      dp.at(i).at(j) = dp.at(i - 1).at(j);

      // i番目の要素を選ぶ場合(選べるときだけ)
      if (j - w.at(i) >= 0) {
        dp.at(i).at(j) = std::max(dp.at(i - 1).at(j),
                                  dp.at(i - 1).at(j - w.at(i)) + v.at(i));
      }
    }
  }

  std::cout << dp.at(N).at(W) << std::endl;

  return 0;
}

実際の提出結果はこちら。

個数制限無しナップザック問題

問題

重さと価値がそれぞれ$w_i$, $v_i$であるような$N$種類の商品がある$(1 \leq i \leq N)$。これらの商品の中から、重さの総和が$W$を超えないように選んだときの、価値の総和の最大値を求めなさい。
ただし、同じ種類の商品はいくつでも選ぶことができる。

DPテーブル

DPテーブルの定義

$dp[i][j]$：$i$番目の商品まで選択対象に含めたとき、重さが$j$以下になるようにいくつかの商品を選んだときの、価値の総和の最大値。ただし、$0 \leq i \leq N, 0 \leq j \leq W$。

初期条件

重さが0ならば、$i$番目までの商品を1つも選んでいないことになるので、価値の総和も0になる。
また、$i = 0$のとき、選べる商品が1つもないので、価値の総和は0になる。

$$\begin{cases} dp[i][0] = 0 \quad (0 \leq i \leq N) \\ dp[0][j] = 0 \quad (0 \leq j \leq W) \end{cases}$$

漸化式

ナイーブな実装

同じ種類の商品をいくつ選んでもよいという条件をナイーブに実装すると、漸化式は以下のようになる。

$$dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - k w_i] + k v_i) \quad (1 \leq i \leq N, 1 \leq j \leq W, 0 \leq k \land k w_i \leq j)$$

$k$は$i$番目の商品の個数である。$k = 0$は$i$番目の商品を選ばないことと等しい。
この漸化式をプログラムに実装すると、以下のようなソースコードになる。

naive

std::vector<std::vector<int64_t>> dp(N + 1, std::vector<int64_t>(W + 1, 0));

for (int64_t i = 1; i <= N; i++) {
  for (int64_t j = 1; j <= W; j++) {
    for (int64_t k = 0; k * w.at(i) <= j; k++) {
      dp.at(i).at(j) = std::max(dp.at(i).at(j),
                                dp.at(i - 1).at(j - k * w.at(i)) + k * v.at(i));
    }
  }
}

この実装では計算量は$\mathcal{O}(NW^2)$となる。制約によっては計算時間をオーバーしてしまう。

この計算量を減らしてみる。
$i$番目の商品をいくつか選ぶとき、すなわち$k \geq 1$のときのことをを考える。$i$番目の商品を$k$個選ぶときというのは、$i$番目の商品をすでに1個選んだときの状態($dp[i][j - w_i]$)から、更に$k - 1$個選ぶことに等しい。そのため、漸化式において、$k \geq 1$の部分の計算は、$dp[i][j - w_i]$の計算を行ったときに終了していることがわかる。

従って、漸化式の右辺を以下のように式変形することが可能となる。

$$\begin{align*} \max(dp[i - 1][j - k w_i] + k v_i | 0 \leq k) &= \max(dp[i - 1][j], dp[i - 1][j - k w_i] + k v_i | 1 \leq k) \\ &= \max(dp[i - 1][j], \max(dp[i - 1][(j - w_i) - k w_i] + k v_i | 0 \leq k) + v_i) \\ &= \max(dp[i - 1][j], dp[i][j - w_i] + v_i) \end{align*}$$

$$dp[i][j] = \begin{cases} dp[i - 1][j] \\ \max(dp[i - 1][j], dp[i][j - w_i] + v_i) \quad (j - w_i \geq 0) \end{cases} \quad (1 \leq i \leq N, 1 \leq j \leq W)$$

基本のナップザック問題における漸化式とほぼ同じ形だが、2段目の式の$\max$関数の2つ目の引数の添字が異なっていることに注意すること。

出力

$dp[N][W]$を出力すればよい。

例題と解答例

• Aizu Online Judge DPL 1_C ナップザック問題

DPL_1_C

#include <iostream>
#include <vector>

int main() {
  int64_t N, W;
  std::cin >> N >> W;
  std::vector<int64_t> w(N + 1);
  std::vector<int64_t> v(N + 1);
  for (int64_t i = 1; i <= N; i++) {
    std::cin >> v.at(i) >> w.at(i);
  }

  std::vector<std::vector<int64_t>> dp(N + 1, std::vector<int64_t>(W + 1, 0));

  for (int64_t i = 1; i <= N; i++) {
    for (int64_t j = 1; j <= W; j++) {
      if (j - w.at(i) >= 0) {
        dp.at(i).at(j) =
            std::max(dp.at(i - 1).at(j), dp.at(i).at(j - w.at(i)) + v.at(i));
      } else {
        dp.at(i).at(j) = dp.at(i - 1).at(j);
      }
    }
  }

  std::cout << dp.at(N).at(W) << std::endl;

  return 0;
}

実際の提出結果はこちら。

ナップザック問題その2

問題

重さと価値がそれぞれ$w_i$, $v_i$であるような$N$個の商品がある$(1 \leq i \leq N)$。これらの商品の中から、重さの総和が$W$を超えないように選んだときの、価値の総和の最大値を求めなさい。

ただし、$W$は大きい($1 \leq W \leq 10^9)$とする。

DPテーブル

DPテーブルの定義

$W$が大きいので、基本のナップザック問題と同じDPテーブルでは計算が間に合わない。
そこで、価値の総和について計算を行うDPテーブルを定義する。

$dp[i][j]$：$i$番目の商品まで選択対象に含めたとき、価値の総和がちょうど$j$になるようにいくつかの商品を選んだときの、重さの総和の最小値(価値の総和がちょうど$j$になるような選び方が存在しないときは無限大の値を取る)。$(0 \leq i \leq N, 0 \leq j \leq \sum{v_i})$

初期条件

$i = 0, j = 0$のとき0とし、その他のDPテーブル要素は正の無限大を初期条件としておく。

$$\begin{cases} dp[0][0] = 0 \quad (i = 0 \land j = 0) \\ dp[i][j] = \infty \quad (\text{other}) \end{cases}$$

漸化式

漸化式の形は、最小値を取ることを除けば基本のナップザック問題とそれほど変わらない。

$$dp[i][j] = \begin{cases} dp[i - 1][j] \quad (j - v_i < 0) \\ \min(dp[i - 1][j], dp[i - 1][j - v_i] + w_i) \quad (j - v_i \geq 0) \end{cases} \quad (1 \leq i \leq N, 1 \leq j \leq \sum{v_i})$$

出力

$dp[N][j] \leq W$を満たす最大の$j$を出力すればよい。

例題と解答例

• AtCoder Educational DP Contest E - Knapsack2

解答例のコードを以下に示す。

E - Knapsack2

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
 
int main() {
  int64_t N, W;
  std::cin >> N >> W;
  std::vector<int64_t> w(N + 1);
  std::vector<int64_t> v(N + 1);
  for (int64_t i = 1; i <= N; i++) {
    std::cin >> w.at(i) >> v.at(i);
  }
 
  int64_t V = std::accumulate(v.begin(), v.end(), static_cast<int64_t>(0));
  // 無限大の代わりとして、十分大きな数(2^60)を初期条件にセットしている
  std::vector<std::vector<int64_t>> dp(N + 1, std::vector<int64_t>(V + 1, 1LL << 60));
 
  dp.at(0).at(0) = 0;
  for (int64_t i = 1; i <= N; i++) {
    for (int64_t j = 0; j <= V; j++) {
      dp.at(i).at(j) = dp.at(i - 1).at(j);
 
      if (j - v.at(i) >= 0) {
        dp.at(i).at(j) = std::min(dp.at(i - 1).at(j), dp.at(i - 1).at(j - v.at(i)) + w.at(i));
      }
    }
  }
 
  int64_t answer = 0;
  for (int64_t i = 1; i <= N; i++) {
    for (int64_t j = 1; j <= V; j++) {
      if (dp.at(i).at(j) <= W) {
        answer = std::max(answer, j);
      }
    }
  }
 
  std::cout << answer << std::endl;
}

実際の提出結果はこちら。

参考文献

• 秋葉拓哉、岩田陽一、北川 宜稔、問題解決のアルゴリズム活用力とコーディングテクニックを鍛える プログラミングコンテストチャレンジブック 第2版、株式会社マイナビ出版、2021年4月12日