読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

部分和問題

Online Judge Algorithm

部分和問題(プログラミングコンテストチャレンジブック p34の設定)

整数a_1,a_2,\dots a_nの中からいくつか選び、その和をちょうどkにすることができるならYes、できないならNoを出力。
制約
1 \leq n \leq 20
-10^8 \leq a_i \leq 10^8
-10^8 \leq k \leq 10^8

アルゴリズム

部分和問題(プログラミングコンテストチャレンジブック p34にあるように深さ優先探索(DFS:Depth-First Search)で解いてみる。
a_iを加えるor加えないで左右に分岐する2分木を考えると、状態数は2^{n + 1}

コード

//※a_1 →a[0]
import java.util.*;
public class subset_sum {
	static Scanner scanner;
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new subset_sum();
	}
	subset_sum(){
		int n = scanner.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) a[i] = scanner.nextInt();
		int k = scanner.nextInt();
		System.out.println( solve(n,a,k) );
	}
	String solve(int n, int[] a, int k){
		return DFS(0,0,n,a,k) ? "Yes" : "No";
	}
	//i(aの添え字、加える or 加えないを決定した個数(深さに相当)), sum(ルートからカレントまで来たときの合計)
	boolean DFS(int i,int sum, int n, int[] a, int k){
		if( i == n ) return sum == k; //n個決め終わったので、sum = k になっているかどうかを判定
		if( DFS(i+1, sum+a[i], n, a, k) ) return true; //a[i]を使う
		if( DFS(i+1, sum, n, a, k) ) return true; //a[i]を使わない
		return false;
	}
}