山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[Aizu Online Judge]全探索 (ALDS1_5_A: Exhausive Search)

全探索

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の6章2節では、全探索のアルゴリズムについてでした。

6章では、再帰・分割統治法を取り扱います。プログラムで再帰といえば、階乗を求めるプログラムが思い浮かびます。

分割統治は、問題の部分問題に分割して解くというものです。例えば、長さnの数値配列が与えられたとき、最大値を見つけよという問題があるとします。このとき、配列を二つに分け、前半の最大値を後半の最大値を比較することで、全体の最大値を求めることが分割統治法に当たります。

ALDS1_5_A: Exhausive Search

pp. 142では全探索についての問題が与えられます。問題は下のサイトから見ることができます。

全探索 | アルゴリズムとデータ構造 | Aizu Online Judge

この問題を解く前に、長さnのビット列を全て列挙することを考えます。長さがnなので、 2^n 通りのビット列が存在します。これは、再帰関数を使うことで列挙することができます。

ビット列を列挙するコード
public class Test {
    public static int []S = new int[3];
    public static int n;
    public static int k;
    public static void main(String[] args) {
        n = 3;
        for(int i = 0; i < n; i++) {
            S[i] = 0;
        }
        rec(0);
    }
    public static void rec(int k) {
        if(k == n) {
            disp(S);
            return;
        }
        rec(k + 1);
        S[k] = 1;
        rec(k + 1);
        S[k] = 0;
    }
    public static void disp(int []A) {
        for(int i = 0; i < A.length - 1; i++) {
            System.out.print(A[i] + ", ");
        }
        System.out.println(A[A.length -1]);
    }
}
解答
import java.util.Scanner;

public class ALDS1_5_A {
    public static int n;
    public static int []A = new int[50];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 0; i < n; i++) {
            A[i] = scan.nextInt();
        }
        int q = scan.nextInt();
        for(int i = 0; i < q; i++) {
            int m = scan.nextInt();
            if(isSolve(0, m)) {
                System.out.println("yes");
            }else {
                System.out.println("no");
            }
        }
        scan.close();
    }
    public static boolean isSolve(int i, int m) {
        if(m == 0) return true;
        if(i >= n) return false;
        boolean res = isSolve(i + 1, m) || isSolve(i + 1, m - A[i]);
        return res;
    }
}