AOJ2080 Compress Files - nanikakaのAOJ航海日誌

概要

N個のファイルがあり、それぞれ、圧縮前のサイズBと圧縮後のサイズAが決まっている。作業領域の初期サイズはMである。
圧縮が済んでいないファイルの集合を選び、1つの圧縮ファイルにまとめることができる。この圧縮ファイルのサイズは、選ばれたファイルのAiの総和である。ただし、この圧縮の作業が行われるためには、出来上がる圧縮ファイルのサイズ以上の作業領域が必要である。圧縮ファイルが作られた後、圧縮に選ばれたファイルが削除され、作業領域として使うことができる。
この圧縮作業を繰り返し、N個のファイル全てを圧縮したときに作りだされる圧縮ファイルの数の最小値を答えよ。不可能な場合はImpossibleとせよ。
1 <= N <= 14
1 <= M <= 1000
Ai <= Bi

解法

未圧縮のファイルの集合は1つの整数値で表すことができます。この整数値に対する幅優先探索で解けます。
ただし、1つの状態数から移れる状態が非常に多いので時間がかなり厳しいです。状態Xから遷移する候補は、Xの部分集合を列挙することにします(蟻本P144)。
状態Xにおける、作業領域の大きさは全て計算することができます。なので、状態XからYへ遷移できるか(作業領域が足りるか)は計算可能です。
これに加えて、無駄な探索をしないための枝刈りを入れることで何とか間に合います。

ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

//Compress Files
public class AOJ2080 {

	int INF = 1<<29;
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), m = sc.nextInt();
			if((n|m)==0)break;
			int[] a = new int[n], b = new int[n];
			for(int i=0;i<n;i++){
				b[i] = sc.nextInt(); a[i] = sc.nextInt();
			}
			int[] dp = new int[1<<n];
			Arrays.fill(dp, INF);
			dp[(1<<n)-1] = 0;
			List<Integer> l = new ArrayList<Integer>();
			l.add((1<<n)-1);
			while(!l.isEmpty()&&dp[0]==INF){
				List<Integer> next = new ArrayList<Integer>();
				for(int S:l){
					int e = m, s = (S-1)&S;
					for(int k=0;k<n;k++)if(((S>>k)&1)==0)e+=b[k]-a[k];
					while(s!=S){
						if(dp[s]==INF){
							int r = 0;
							for(int k=0;k<n;k++)if(((S>>k)&1)>0&&((s>>k)&1)==0)r+=a[k];
							if(r<=e){
								dp[s] = dp[S]+1; next.add(s);
							}
						}
						s = (s-1)&S;
					}
				}
				l = next;
			}
			System.out.println(dp[0]==INF?"Impossible":dp[0]);
		}
	}

	public static void main(String[] args) {
		new AOJ2080().run();
	}
}