Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-03SRM350, SRM351, SRM352 (Practice)

SRM 352 FibonacciKnapsack

|  SRM 352 FibonacciKnapsack - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 352 FibonacciKnapsack - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7481

  • メモ化再帰。
    • 枝刈りを仕込むとうまくいく。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class FibonacciKnapsack {

	class Item implements Comparable<Item> {
		long w;
		long v;
		Item(long _w, long _v) {
			w = _w;
			v = _v;
		}
		public int compareTo(Item arg0) {
			if (w == arg0.w) {
				return Long.signum(arg0.v - v);
			}
			return Long.signum(arg0.w - w);
		}
	}
	
	Item[] it;
	long[] sumw;
	long[] sumv;
	
	Map<Long, Long> m[];
	
	public long dfs(int i, long now) {
		if (i >= it.length) {
			return 0;
		}
		if (m[i].containsKey(now)) {
			return m[i].get(now);
		}
		
		long ret = 0;
		if (now >= sumw[i]) {
			ret = sumv[i];
		} else {
			ret = Math.max(ret, dfs(i+1, now));
			if (now >= it[i].w) {
				ret = Math.max(ret, dfs(i+1, now - it[i].w) + it[i].v);
			}
		}
		
		m[i].put(now, ret);
		return ret;
	}
	
	public long maximalCost(String[] items, String C) {
		int len = items.length;
		it = new Item[len];
		for (int i = 0 ; i < len ; i++) {
			String[] data = items[i].split(" ");
			long a = Long.valueOf(data[0]);
			long b = Long.valueOf(data[1]);
			it[i] = new Item(a, b);
		}
		Arrays.sort(it);
		
		sumw = new long[len+1];
		sumv = new long[len+1];
		for (int i = 0 ; i < len ; i++) {
			long v = 0;
			long w = 0;
			for (int j = i ; j < len ; j++) {
				w += it[j].w;
				v += it[j].v;
			}
			sumw[i] = w;
			sumv[i] = v;
		}
		
		m = new Map[len];
		for (int i = 0 ; i < len ; i++) {
			m[i] = new HashMap<Long, Long>();
		}

		return dfs(0, Long.valueOf(C));
	}
}