部分和問題を切る！

DP(Dynamic Programming)の題材として、部分和問題を取り上げよう。

部分和問題はこんな感じ。

与えられた集合Aと整数Kに対して、
sum(A') = KとなるようなAの部分集合A'は存在するか？
※ここでsum(X)は集合Xの全要素の和である。

ちょっと、分かりにくいかもしれないので簡単な例題を。

A = {1, 3, 5, 12, 7}

K = 11

に対して、sum(A') = K となるようなAの部分集合A'は存在するか？

答えは、yes.

Aの部分集合A' = {1,3,7}の全要素の和は11だからである。

ということで、これをコーディングしてみよう。

普通に考えると、Aの部分集合を逐次抽出して行って、sum(A') == Kとなった時点で終了判定してループ抜ければいいのかなって感じだろう。。

しかし、Aの部分集合は全部で、2^|A|となってしまう。（|A|はAの要素数）

ということは、最悪計算量は、2^|A|である。これは、まずい。。。

とりあえず、ソースコードはこんな感じ。。

#define forf(i, n) for(int i=0; i<(int)(n); i++)

vector<int> subsetSum(vector<int> set, int K) {
vector<vector<int> > subset;
vector<int> phi;
subset.push_back(phi);

forf(i, set.size()) {
 vector<vector<int> > newSubset;
 forf (j, subset.size()) {
  vector<int> subsetElm = subset[j];
  subsetElm.push_back(set[i]);
  int sum = 0;
  forf (k, subsetElm.size())
   sum += subsetElm[k];
  if (sum == K)
   return subsetElm;
  newSubset.push_back(subsetElm);
 }

 forf(j, newSubset.size())
  subset.push_back(newSubset[j]);
}

return vector<int> ();
}

さて、ここで気付いて欲しい。

上記のコードでは、sum(A') = KとなるA'をreturnしているが、もともとの問題は、sum(A') = KとなるA'が存在するかどうかだったのではないか。。

つまり、A'を出力しなくても、A'が存在するかどうかを出力すればいいのである。（このような問題を判定問題（または、決定問題）と呼びます。PとかNPとか言ってるやつは、実は判定問題に対するクラスの名称です。なので、決定問題じゃない問題に対してPとかNPとか言うのは間違いです。）

と、PとかNPはちょっと話が脱線してしまったが、

部分和問題は、条件を満たす部分集合の存在を問うているので

その部分集合を出力する必要はない。ということは‥部分集合を生成したり保持しなくてもいいんじゃないの？？

この辺りにトリックが隠されてそうである。

この問題をDPでどのように多項式時間の解法に持ち込むか。

次回に続く・・・・・