AOJ2333 My friends are small

AOJ Volume23

問題リンク My friends are small

  • 解法

強引気味なメモ化探索で解きました。
まず思いついた方針は、重さwiを降順でソートし、
mem[i][j][k]: リュックの残り重量j、i番目以前の重さで使用しなかったものの最小値がkのとき、i番目以降を使ってリュックにつめる組み合わせ数
という表を埋めるようなメモ化探索です。ですがこれだと、N^2 * Wの大きさになってメモリが足りなくて困ります。でも、実際に使用する(i,j,k)の組み合わせはそれほど多くなく、使わない領域がかなりあるんじゃないかと予想したので、Map[i][j]というMapの2次元配列にし、kをMapのキーにするという方法でN^2*Wの表を用意することを回避しました。他の方の解よりは遅いですけど通りました。

  • ソース
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//My friends are small
public class AOJ2333 {

	int n, W, MOD = 1000000007;
	int[] w;
	Map<Integer, Integer>[][] mem;
	
	int get(int k, int rest, int min){
		if(rest<0)return 0;
		if(k<0)return rest<min?1:0;
		if(mem[k][rest].containsKey(min))return mem[k][rest].get(min);
		int res = (get(k-1, rest, w[k])+get(k-1, rest-w[k], min))%MOD;
		mem[k][rest].put(min, res);
		return res;
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); W = sc.nextInt();
		w = new int[n];
		for(int i=0;i<n;i++)w[i]=sc.nextInt();
		Arrays.sort(w);
		mem = new Map[n][W+1];
		for(int i=0;i<n;i++)for(int j=0;j<=W;j++)mem[i][j]=new HashMap<Integer, Integer>();
		System.out.println(get(n-1, W, 1<<29));
	}
	
	public static void main(String[] args) {
		new AOJ2333().run();
	}
}