AOJ0182 Beaker

問題リンク Beaker

• 解法

DFS+貪欲で解けました。
一番大きいビーカーの水を小さいビーカーへ振り分けるやり方は非常に多くなるのでたぶん時間が厳しいです。ここで逆転の発想、全てのビーカーに水を注ぐことができた時、最後に水が入っているビーカーはどこかを先に決めます。水は最初maxの容量しかないので、最後に水が入っているビーカーの容量の総和もmaxです。ここが決まると（証明したわけではないので常に成り立つかは分からないんですが）、貪欲的に解の判定ができます。
ビーカーは容量の昇順でソートされているものとします。
容量の小さい方から順に見ていき、水が入っているビーカーはスルーします。水が入っていないビーカー i を見つけた場合次のことをします
・i未満のビーカーのうち、水が入っているものを使って、ビーカーiの容量を作りだす（採用するビーカーは大きいものを優先して採用するようにする）
・ビーカーiの容量を作るのに採用したビーカーから水を抜いて、ビーカーiに水を入れる
・ビーカーiの容量を作り出せなかったら、初期値の水の割り当て方は失敗
これは、大きいビーカーから小さいビーカーへ注ぐという行為の逆から考えているため、小さいビーカーの水を集めて、大きいビーカーへ入れるということをしています。このとき、なるべく大きいビーカーから使うようにします。小さいビーカーを残すほど、後々細かい調整ができるので有利に働きそうだからです。
水が入っていないビーカーを見つけ次第、このように貪欲的に水を集め、最後のビーカーまでこの処理が成功した場合、解がYESとなります。
自明ですが、容量の一番小さいビーカーは最初、必ず水が入ります。

ソースの補足
dfs: 初期の水の割り当てを決める再帰関数。割り当てが決まったらgreedy()を呼ぶ
greedy: 容量の小さいビーカーから見ていき、空のビーカーを見つけたらchoice()を呼んでビーカーに水を入れる
choice: 容量の大きいビーカーを優先して使いながら、水を集める再帰関数

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Beaker
public class AOJ0182 {

	int n;
	int[] a;
	boolean[] have, t;
	
	boolean dfs(int k, int rest){
		if(rest==0){
			for(int i=0;i<n;i++)t[i]=have[i];
			return greedy();
		}
		if(rest < a[k])return false;
		have[k] = true;
		if(dfs(k+1, rest-a[k]))return true;
		have[k] = false;
		return dfs(k+1, rest);
	}
	
	boolean choice(int k, int rest){
		if(rest==0)return true;
		if(k<0)return false;
		if(!t[k])return choice(k-1, rest);
		if(a[k]<=rest){
			t[k] = false;
			if(choice(k-1, rest-a[k]))return true;
			t[k] = true;
		}
		return choice(k-1, rest);
	}
	
	boolean greedy(){
		for(int i=0;i<n;i++)if(!t[i]){
			if(!choice(i-1, a[i]))return false;
			t[i] = true;
		}
		return true;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		t = new boolean[100];
		have = new boolean[100];
		for(;;){
			n = sc.nextInt();
			if(n==0)break;
			a = new int[n];
			for(int i=0;i<n;i++){
				a[i] = sc.nextInt();
			}
			Arrays.sort(a);
			Arrays.fill(have, false);
			have[0] = true;
			System.out.println(dfs(1, a[n-1]-a[0])?"YES":"NO");
		}
	}
	
	public static void main(String[] args) {
		new AOJ0182().run();
	}
}