Exhaustive Search [ AIZU ONLINE JUDGE ALDS1_5_A ]

judge.u-aizu.ac.jp

数列 A と m 個の数値が与えられる。m 個の数値のそれぞれについて、数列 A のいくつかの要素を足し合わせて作ることができるなら yes 、作れないなら no を出力せよという問題です。

この問題、いろいろな解き方があると思うんですけど、私は（比較的得意な）ビット全探索で解くことにしました。

まず、数列 A から作ることのできる全ての部分集合（の和）を、あらかじめ Set に詰め込んでしまいます。こうしてしまえば、それぞれの m について、Set の中に含まれているかどうかで簡単に判定することができます。

void solve () {

	int n = nextInt();
	int[] A = nextIntArray(n);

	//ビット全探索でAの部分集合の和を全てSetに詰め込む
	HashSet<Integer> set = new HashSet<>();
	for (int i=0; i<Math.pow(2,n); i++) {
		int tempSum = 0;
		for (int j=0; j<n; j++) {
			if ((1&i>>j) == 1) {
				tempSum += A[j];
			}
		}
		set.add(tempSum);
	}

	//mがSetに含まれているかどうかで判定する
	int m = nextInt();
	for (int i=0; i<m; i++) {
		out.println(set.contains(nextInt())? "yes" : "no");
	}

}

今回の記事から、試験的に、解答コードを solve 関数の部分のみ記載することにしました。

Fast Scanner やその他の便利関数などを解答コードに埋め込んで使うようになったので、ブログに記載するたびにそれらを削除するのが面倒くさくなったためです。変数名や関数名などは極力わかりやすいものを採用していますので、何をやっているのかわからないということは多分ないだろうと思うんですが、もし何かあれば遠慮なく指摘してやってください。

ちなみに、今回の記事では以下のような関数・変数を使用しています。

・nextInt() …… 次のint型整数を取得する
・nextIntArray(n) ...... 次のint型整数をn個取得してint型配列に代入する
・out.println() ...... PrintWriter による出力