部分和問題を解くアルゴリズムをプログラミングしてみる

部分和問題

ちょうど部分和問題について触れることがあったので，久しぶりにプログラミングの練習．

部分和問題とは，

与えられた n 個の整数 a1,...,an から部分集合をうまく選んで、その集合内の数の和が与えられた数 N に等しくなるようにできるかどうかを判定する問題

という問題．(部分和問題 - Wikipediaより)

例えば，{1,2,3,4,5,6}のうちいくつかを足して21にできるかどうか，という問題．

これを解くアルゴリズムとして，

  • {1,2,3,4,5,6}の一つ一つについて選ぶか選ばないかを決め，
  • そのそれぞれの選び方で選んだ数の和のうち，21になるものがあればYESと判定
  • 一つも21になるものがなければNOと判定

を採用．

選ぶか選ばないか2通りの選択が，{1,2,3,4,5,6,7}の集合の要素数分だけあるから，
要素数が増えれば計算量は指数関数的に増えていく．．．

PHPでプログラミング

整数の集合は配列(変数$S)で，与えられた数は変数$tで宣言．

まずはアルゴリズムの通りに実装したいので，再帰関数を使用．
集合から一つ数を取り出して，その数を選ぶ場合と選ばない場合に再帰を用いて分岐．

選ぶ数は別の配列に保存して，集合が空になったときに選んだ数を足し合わせて判定．

<?php
$S = array(1, 2, 3, 4, 5);
$t = 21;

bubun($S, array());
print "NO\n";

function bubun($S, $a){
	global $t;
	if(empty($S)){
		$i = array_sum($a);
		if($i == $t){
			var_dump($a);
			exit();
		}
	}else{
		$i = array_pop($S);
		bubun($S, $a);
		array_push($a, $i);
		bubun($S, $a);
	}
}
?>

問題としては，選んだ数を表示しなくてもいいから(判定するだけでよい)，
変数$tから値を引く・引かないで選ぶ・選ばないを分岐させて，

<?php
$S = array(1, 2, 3, 4, 5, 6);
$t = 21;

bubun($S, $t);
print "NO\n";

function bubun($S, $t){
	if($t == 0){
		print "YES\n";
		exit();
	}elseif(empty($S)){
		return;
	}
	$i = array_pop($S);
	bubun($S, $t);
	bubun($S, $t-$i);
}
?>

再帰ではなくて，繰り返しでできないか，ということで，，
新たに，足し合わせた数を格納する配列を用意して，

  • 集合から一つずつ値を取り出す
    • 配列をコピー
    • 一方には取り出した値を足し合わせる
    • 配列をくっつける

という感じで，足す・足さないで選ぶ・選ばないを実現

<?php
$S = array(1, 2, 3, 4, 5, 6, 7);
$t = 21;
$sum = array();

for($temp = $S; !empty($S); $temp = $sum){
	$a = array_pop($S);
	for($i=0; $i<count($sum); $i++) $sum[$i] = $sum[$i] + $a;
	$sum = array_merge($sum, $temp);
}

array_search($t, $sum) ? print "YES\n": print "NO\n";
?>

SQLで実現

部分和問題でググってたら，SQLで解くという話がおもしろかった．

サービス終了のお知らせ - Yahoo!ジオシティーズ
http://d.hatena.ne.jp/kano-e/20070809/1186672517

CやPHPと違って構造化プログラミングができないから，解くのが難しい．
上記のリンクのkano-e no memoさんの方法が一番良いんじゃないかと．

  • 0と1が入ったbool表を用意
  • bool表を集合の要素回だけ結合(直積して要素数桁のすべてのビットパターンを生成)
  • 1が現れた場所に各要素を外部結合
  • 選んだ要素を足し合わせて，目的の行を選択

って感じかな．

外部結合部分で少し削れそうな部分があったので，いじってみる．
集合の各要素はSQL文の中に書いちゃって，それを保存しておくテーブルはいらなくなるかも．

SELECT n1, n2, n3, n4, n5
  FROM (
    SELECT
      a, b, c, d, e,
      coalesce(n1.id, 0) n1,
      coalesce(n2.id, 0) n2,
      coalesce(n3.id, 0) n3,
      coalesce(n4.id, 0) n4,
      coalesce(n5.id, 0) n5
      FROM (
        SELECT a.id a, b.id b, c.id c, d.id d, e.id e
          FROM bool a, bool b, bool c, bool d, bool e
      ) as f
      LEFT JOIN ( SELECT 1 id ) as n1 ON a = 1
      LEFT JOIN ( SELECT 2 id ) as n2 ON b = 1
      LEFT JOIN ( SELECT 3 id ) as n3 ON c = 1
      LEFT JOIN ( SELECT 4 id ) as n4 ON d = 1
      LEFT JOIN ( SELECT 5 id ) as n5 ON e = 1
  ) as ssp
  WHERE
    n1 + n2 + n3 + n4 + n5 = 7
;