部分和問題を切る！ Part2

ぶった切れ～～。。
部分和問題なんて楽勝じゃーー。。笑

前回に引き続き部分和問題について。
今回は、動的計画法で解いてみましょう。。

sub(A') == K となるA'を列挙するのではなく、そのようなA'が存在するかどうかを提示するだけでいいというのがポイントであることは前回ちょろっと述べました。。

つまりメモリ上にキャッシュしておくべき情報は、部分集合のすべての要素ではなく、すべてのA'に対するsub(A')の和だけでいいのです！！
これちょっと分かりにくいので、ソースコードみて何を言わんとしているか理解して下さい。

まずは、これ。Aの部分集合A'をすべてキャッシュしています。
割り当てられるメモリサイズはO(2^|A|)です。

view plainprint?

1. bool subsetSumAll(vector<int> set, int K) {  
2. vector<vector<int> > subset;  
3. vector<int> phi;  
4. subset.push_back(phi);  
5.   
6. forf(i, set.size()) {  
7.  vector<vector<int> > newSubset;  
8.  forf (j, subset.size()) {  
9.   vector<int> subsetElm = subset[j];  
10.   subsetElm.push_back(set[i]);  
11.   int sum = 0;  
12.   forf (k, subsetElm.size())  
13.    sum += subsetElm[k];  
14.   if (sum == K)  
15.    return true;  
16.   newSubset.push_back(subsetElm);  
17.  }  
18.   
19.  forf(j, newSubset.size())  
20.   subset.push_back(newSubset[j]);  
21. }  
22.   
23. return false;  
24. }  

bool subsetSumAll(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 true;
  newSubset.push_back(subsetElm);
 }

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

return false;
}

※一部、実装高速化のためのマクロを使用しています。

これに対し、sum(A')の値をキャッシュする場合。このとき、Aの要素はすべて自然数でかつsum(A') == KとなるA'を探せばいいことから、状態をキャッシュするために用意すべき配列サイズはO(K)です。

view plainprint?

1. bool subsetSumDp(vector<int> set, int K) {  
2. int num[K + 1];  
3. int num_t[K + 1];  
4.   
5. memset(num, 0, sizeof(num));  
6. forf(i, set.size()) {  
7.   
8.  memcpy(num_t, num, sizeof(num));  
9.  forf(j, K+1) {  
10.   if (!num[j])  
11.    continue;  
12.   if (j + set[i] > K)  
13.    continue;  
14.   num_t[j + set[i]] = 1;  
15.  }  
16.  if (set[i] < K+1)  
17.   num_t[set[i]] = 1;  
18.  memcpy(num, num_t, sizeof(num_t));  
19.  if (num[K])  
20.   return true;  
21. }  
22. return false;  
23. }  

bool subsetSumDp(vector<int> set, int K) {
int num[K + 1];
int num_t[K + 1];

memset(num, 0, sizeof(num));
forf(i, set.size()) {

 memcpy(num_t, num, sizeof(num));
 forf(j, K+1) {
  if (!num[j])
   continue;
  if (j + set[i] > K)
   continue;
  num_t[j + set[i]] = 1;
 }
 if (set[i] < K+1)
  num_t[set[i]] = 1;
 memcpy(num, num_t, sizeof(num_t));
 if (num[K])
  return true;
}
return false;
}

上に示した2つのプログラムは同一の解を出力します。なんか騙されたような感じです。
もうちょっと踏み込んで考えてみましょう。
A={1,2,3,4,5,6,7,8,9,10}, K = 5
としましょう。

sum(A') == K となるA'を探してみましょう。これくらいなら、人間でもできますね（笑）

A' ={2, 3}
A' = {1,4}
A' = {0,5}

はい、1つの値Kに対して、sum(A') == Kを満たすA'が複数存在しますね。。
A -> φ(A)
なる写像φががうまく作用して問題をAの世界ではなく、φ(A)の世界で考えているような感じです。これが何となく騙されたようなトリックじゃないでしょうか。。

さてさて、では、上記2つの実行速度を比較してみましょう。

view plainprint?

1. #define PRB_SIZE 20  
2.   
3. int main() {  
4. // init the problem  
5. vector<int> set;  
6. forf(i, PRB_SIZE)  
7.  set.pb(rand() % 100 + 1);  
8.   
9. int sum = 0;  
10. forf(i, PRB_SIZE)  
11.  sum += set[i];  
12.   
13.   
14. // All Possible Combination Search  
15. double start_t = gettimeofday_sec();  
16. forf(k, sum)  
17.  cout << "k = " << k << ": " << subsetSumAll(set, k) << endl;  
18. cout << gettimeofday_sec() - start_t << endl;  
19.   
20. // DP  
21. start_t = gettimeofday_sec();  
22. forf(k, sum)  
23.  cout << "k = " << k << ": " << subsetSumDp(set, k) << endl;  
24. cout << gettimeofday_sec() - start_t << endl;  
25.   
26. // Proof Calculation  
27. forf(k, sum)  
28.  if(subsetSumDp(set, k) != subsetSumAll(set, k))  
29.   cout << "The two outputs are different!!" << endl;  
30. return 0;  
31. }  

#define PRB_SIZE 20

int main() {
// init the problem
vector<int> set;
forf(i, PRB_SIZE)
 set.pb(rand() % 100 + 1);

int sum = 0;
forf(i, PRB_SIZE)
 sum += set[i];


// All Possible Combination Search
double start_t = gettimeofday_sec();
forf(k, sum)
 cout << "k = " << k << ": " << subsetSumAll(set, k) << endl;
cout << gettimeofday_sec() - start_t << endl;

// DP
start_t = gettimeofday_sec();
forf(k, sum)
 cout << "k = " << k << ": " << subsetSumDp(set, k) << endl;
cout << gettimeofday_sec() - start_t << endl;

// Proof Calculation
forf(k, sum)
 if(subsetSumDp(set, k) != subsetSumAll(set, k))
  cout << "The two outputs are different!!" << endl;
return 0;
}

全件検索の場合: 524.896(s)
DPの場合 : 0.189(s)

はい（笑）違いは明白です。。
メモリの制限から考えて全件検索の場合は、|A| >= 26くらいになると解くのは不可能でしょう。。
ちなみにwindowsの場合は、メモリ制限は2GBまでです。
|A| = 26の集合Aのすべての部分集合をキャッシュするために必要なリストのサイズは、

部分集合の数 * 部分集合のサイズ * intのサイズ(B)

= 2^26 * 26/2 * 4 = 3.49GB

※部分配列のサイズは、簡単のため|A|/2としています。

こりゃ、解けないわー。。
実際|A| = 26の規模の問題を解くと、以下のエラーが（笑）

This application has requested the Runtime to terminate it in an unusual way.

Please contact the application's support team for more information.

いや、Dynamic Programmingの真髄を見た感じがします。