パーティション問題とは？動的計画法で「等しい合計の2つの部分集合」への分割を判定する方法

パーティション問題とは、与えられた整数の集合を、それぞれの部分集合の要素の合計が等しくなるように2つに分割できるかどうかを判定する古典的なアルゴリズム問題です。

まず、与えられた集合の全要素の合計値を求めます。合計が偶数であれば、2つの集合へ分割できる可能性があります。一方、合計が奇数の場合は、合計の等しい2つの集合に分割することは不可能です。

合計が偶数である場合、「partTable」という名前の表（DPテーブル）を作成し、次の条件に基づいて問題を解いていきます。

partTable[i, j] は、array[0] から array[j-1] までの要素から選んだ部分集合の合計が i と一致するときに true、そうでないときに false となります。

入力と出力

入力：
整数の集合 {3, 1, 1, 2, 2, 1}

出力：
集合を合計が等しい2つの部分に分割できる場合は true。
この例では答えは true。分割の一例は {3, 1, 1} と {2, 2, 1}

アルゴリズム

checkPartition(set, n)

入力 − 与えられた集合、およびその要素数 n。

出力 − 合計が等しい2つの部分集合への分割が可能な場合に true。

Begin
    sum := 集合内の全要素の合計
    if sum が奇数 then
        return false

    (sum/2 + 1) × (n + 1) のサイズで partTable を定義
    0行目のすべての要素を true に設定
    0列目のすべての要素を false に設定

    for i in range 1 to sum/2, do
        for j in range 1 to n, do
            partTab[i, j] := partTab[i, j-1]
            if i >= set[j-1], then
                partTab[i, j] := partTab[i, j] or partTab[i - set[j-1], j-1]
        done
    done

    return partTab[sum/2, n]
End

C++ での実装例

#include <iostream>
using namespace std;

bool checkPartition (int set[], int n) {
    int sum = 0;

    for (int i = 0; i < n; i++)      // 集合の全要素の合計を求める
        sum += set[i];

    if (sum%2 != 0)                  // 合計が奇数なら2つの集合には分割できない
        return false;

    bool partTab[sum/2+1][n+1];      // パーティションテーブルを作成
    for (int i = 0; i <= n; i++)
        partTab[0][i] = true;        // 要素0個の集合（合計0）は常に成立するため true

    for (int i = 1; i <= sum/2; i++)
        partTab[i][0] = false;       // 先頭列は空集合を表すため false

    // ボトムアップ方式でパーティションテーブルを埋める
    for (int i = 1; i <= sum/2; i++) {
        for (int j = 1; j <= n; j++) {
            partTab[i][j] = partTab[i][j-1];
            if (i >= set[j-1])
                partTab[i][j] = partTab[i][j] || partTab[i - set[j-1]][j-1];
        }
    }
    return partTab[sum/2][n];
}

int main() {
    int set[] = {3, 1, 1, 2, 2, 1};
    int n = 6;

    if (checkPartition(set, n))
        cout << "与えられた集合は、合計が等しい2つの部分集合に分割できます。";
    else
        cout << "与えられた集合は、合計が等しい2つの部分集合に分割できません。";
}

出力結果

与えられた集合は、合計が等しい2つの部分集合に分割できます。

計算量について

この動的計画法によるアプローチでは、テーブルのサイズが (sum/2 + 1) × (n + 1) となるため、時間計算量・空間計算量はいずれも O(sum × n) です。総当たりですべての分割パターンを試す指数時間の手法と比べ、要素数や合計値が大きくなっても現実的な時間で解ける点が大きな利点です。