部分和問題はこんな感じ。
与えられた集合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でどのように多項式時間の解法に持ち込むか。
次回に続く・・・・・
0 件のコメント:
コメントを投稿