2次元の動的計画法まとめ 部分和問題編

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

基本の部分和問題

問題

配列$A = (a_1, a_2, a_3, \ldots, a_N)$と整数$M$が与えられる。
配列$A$の要素の中からいくつか選び、それらの総和を$M$にできるかどうか判定しなさい。

DPテーブル

DPテーブルの定義

$dp[i][j]$：$i$番目までの$A$の要素を選択対象に含めたとき、その中からいくつか選んで総和をちょうど$j$にできるかどうかの真偽値。($0 \leq i \leq N$)

初期条件

$A$の要素を1つも選ばなければ、総和は$0$になるので、$j = 0$のとき常に真である。
その他の要素は偽としておく。

$$\begin{cases} dp[i][0] = \text{true} \\ dp[i][j] = \text{false} \quad (j \neq 0) \end{cases}$$

漸化式

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

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

の2通りが考えられる。

$i$番目の要素を選ばないとき、$i - 1$番目の要素までを選択対象に含めた時点で総和をちょうど$j$にできる組み合わせが存在していたならば、$i$番目の要素を選択対象に含めたときも当然総和をちょうど$j$にできる組み合わせが存在することになる。

$i$番目の要素を選ぶとき、$i - 1$番目の要素までを選択対象に含めた時点で、総和をちょうど$j - a_i$にできる組み合わせが存在していたならば、$i$番目の要素を選択することによって、総和をちょうど$j$にできる。

これらを踏まえると、漸化式は以下のようになる。

$$dp[i][j] = \begin{cases} dp[i][j] \lor dp[i - 1][j] \\ dp[i][j] \lor dp[i - 1][j - a_i] \quad (j - a_i \geq 0) \end{cases} \quad (1 \leq i \leq N, 1 \leq j \leq M)$$

出力

$dp[N][M]$の真偽を確かめ、適切な解答を出力すればよい。

例題と解答例

例題

• アルゴ式 部分和問題

解答例

アルゴ式 部分和問題の C++解答例のソースコードを以下に示す。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main() {
  // 入力受け取り
  int64_t N, M;
  std::cin >> N >> M;
  std::vector<int64_t> A(N + 1);
  for (int64_t i = 1; i <= N; i++) {
    std::cin >> A.at(i);
  }

  // DPテーブル
  std::vector<std::vector<bool>> dp(N + 1, std::vector<bool>(M + 1, false));
  // 初期条件
  for (int64_t i = 0; i <= N; i++) {
    dp.at(i).at(0) = true;
  }

  // 遷移
  for (int64_t i = 1; i <= N; i++) {
    for (int64_t j = 1; j <= M; j++) {
      // i番目の要素を選ばないとき
      dp.at(i).at(j) = dp.at(i).at(j) || dp.at(i - 1).at(j);

      // i番目の要素を選ぶとき
      if (j - A.at(i) >= 0) {
        dp.at(i).at(j) = dp.at(i).at(j) || dp.at(i - 1).at(j - A.at(i));
      }
    }
  }

  // 出力
  if (dp.at(N).at(M)) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  return 0;
}

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

個数制限あり部分和問題

問題

配列$A = (a_1, a_2, a_3, \ldots, a_N)$、$B = (b_1, b_2, \ldots, b_N)$および整数$M$が与えられる。
配列$A$の要素の中からいくつか選び、それらの総和を$M$にできるかどうか判定しなさい。
ただし、整数$a_i$は$b_i$個まで選ぶことができる。

DPテーブル

DPテーブルの定義

$dp[i][j]$：$i$番目までの要素を選択対象として、総和をちょうど$j$にできたとき、使わずに余る$i$番目の要素の個数の最大値。

総和をちょうど$j$にできないならばDPテーブルの値は$-1$にする。

初期条件

$dp[0][0] = 0$

漸化式

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

1. $i$番目の要素を1つも使わない(使う必要が無い)
2. $i$番目の要素を何個使っても総和をちょうど$j$にできない
3. $i$番目の要素をいくつか使って総和をちょうど$j$にできる

の3通りが考えられる。

$i - 1$番目の要素までを選択対象に含めた時点で総和をちょうど$j$にできるとき、すなわち$dp[i - 1][j]$の値が$-1$ではない場合は、$i$番目の要素を1つも使わずに総和をちょうど$j$にできる。したがって、$i$番目の要素は丸々$b_i$個残るので、$dp[i][j] = b_i$とする。

逆に、$i$番目までの要素を選択対象に含めているとき、$dp[i][j - a_i] \leq 0$、すなわち総和をちょうど$j - a_i$にした時点で$a_i$を使い切ってしまったときは、総和をちょうど$j$にすることができないため、$dp[i][j] = -1$とする。
また、$j < a_i$のときは$a_i$を選んだ時点で総和が$j$を超えてしまうため、どうやっても条件を満たせないので$-1$とする。

最後に、$i$番目までの要素を選んで総和をちょうど$j - a_i$にできていたとき、もう1個$a_i$を使えば総和を$j$にできるので、$dp[i][j] = dp[i][j - a_i] - 1$となる。

以上を踏まえると、漸化式は以下のようになる。

$$dp[i][j] = \begin{cases} b_i \quad (dp[i - 1][j] \geq 0) \\ -1 (j < a_i \lor dp[i][j - a_i] \leq 0) \\ dp[i][j - a_i] - 1 \end{cases}$$

出力

$dp[N][M]$が$-1$ならばNo、そうでなければYesを出力する。

例題と解答例

例題

• アルゴ式 個数制限付き部分和問題

解答例

アルゴ式 個数制限付き部分和問題のC++解答例ソースコードを以下に示す。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

int main() {
  int64_t N, M;
  std::cin >> N >> M;
  std::vector<int64_t> A(N);
  std::vector<int64_t> B(N);
  for (int64_t i = 0; i < N; i++) {
    std::cin >> A.at(i) >> B.at(i);
  }

  // DPテーブル
  std::vector<std::vector<int64_t>> dp(N + 1, std::vector<int64_t>(M + 1, -1));
  // 初期条件
  dp.at(0).at(0) = 0;

  // 遷移
  for (int64_t i = 1; i <= N; i++) {
    for (int64_t j = 0; j <= M; j++) {
      if (dp.at(i - 1).at(j) >= 0) {
        // i番目の要素を使わずに済む場合
        dp.at(i).at(j) = B.at(i - 1);
      } else if (j < A.at(i - 1) || dp.at(i).at(j - A.at(i - 1)) <= 0) {
        // i番目の要素を何個使っても総和をちょうどjにできない
        dp.at(i).at(j) = -1;
      } else {
        // i番目の要素をいくつか使って総和をちょうどjにできる
        dp.at(i).at(j) = dp.at(i).at(j - A.at(i - 1)) - 1;
      }
    }
  }

  // 出力
  if (dp.at(N).at(M) >= 0) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  return 0;
}

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

参考文献

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