C++で指定した合計値になる最大サイズの部分集合を求める方法

問題文

N個の要素からなる配列と合計値が与えられたとき、要素の合計が指定された値と一致する「最大サイズの部分集合」のサイズを求める問題です。

例

入力配列が arr = { 2, 3, 5, 10 }、合計値が sum = 20 の場合、出力は 4 になります。

なぜなら、

2 + 3 + 5 + 10 = 20

となり、配列の全要素を選んだ部分集合の合計が指定された合計値と一致するためです。

アルゴリズム

この問題は動的計画法（DP）を用いて効率的に解くことができます。

まず、通常の部分和問題と同様に subset[i][j] というブール型のDPテーブルを用意します。これは「最初の j 個の要素だけで合計 i を作れるか」を表します。

さらに、部分集合の最大サイズを数えるために、もう1つのDP配列（count 配列）を使用します。count[i][j] は、次の2つのうち大きい方の値を持ちます。

• count[i][j-1] … 現在の要素を採用しない場合
• count[i - X][j-1] + 1 … 現在の要素 X を部分集合に採用する場合

これにより、合計が i となる部分集合の中で、要素数が最大のもののサイズを求められます。計算量は O(sum × n) です。

実装例

#include<bits/stdc++.h>
using namespace std;
int isSubsetSum(int set[], int n, int sum) {
   bool subset[sum + 1][n + 1];
   int count[sum + 1][n + 1];
   for (int i = 0; i <= n; i++) {
   subset[0][i] = true;
      count[0][i] = 0;
   }
   for (int i = 1; i <= sum; i++) {
      subset[i][0] = false;
      count[i][0] = -1;
   }
   for (int i = 1; i <= sum; i++) {
      for (int j = 1; j <= n; j++) {
         subset[i][j] = subset[i][j - 1];
         count[i][j] = count[i][j - 1];
         if (i >= set[j - 1]) {
            subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
            if (subset[i][j]) {
               count[i][j] = max(count[i][j - 1], count[i - set[j - 1]][j - 1] + 1);
            }
         }
      }
  }
  return count[sum][n];
}
int main() {
   int set[] = { 2, 3, 5, 10 };
   int sum = 20;
   int n = 4;
   cout<< "Result = " << isSubsetSum(set, n, sum) << endl;
}

出力

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Result = 4

この結果は、合計が 20 になる部分集合として最大 4 個の要素（{2, 3, 5, 10}）を選べることを示しています。