TopCoder SRM 352 Div1 Medium FibonacciKnapsack

問題

n個の品物があり、それぞれの重さはw[i],価値はp[i]である。
重さCまで入るナップサックに、品物を価値の和が最大になるように詰める。
(一つの品物は一度だけ使える)

ナップサックに入る品物の価値の和の最大値を求めよ。
ただし、w[i]は全てフィボナッチ数である。

制約条件

n≦50
w[i],p[i]≦10^16
C≦10^16
w[i]は全てフィボナッチ数

方針

メモ化再帰


品物を大きいほうから見ていく。
rec(pos,rest)を、pos番目の品物まで見たとき、残りの容量がrestであるときの価値の最大値とする。
その時点で、pos番目以降の品物を全て入れられるとき、全部つめたものを返すという枝刈りを入れると、めちゃくちゃ高速に終わる。

ソースコード

最悪ケース5msくらい。

map<ll,ll> dp[50];
vector<pair<ll,ll> > v,sum;
ll rec(int c,ll rest){
	if(c<0)return 0;
	if(sum[c].first<=rest)return sum[c].second;
	if(dp[c].count(rest))return dp[c][rest];
	ll &res=dp[c][rest];
	if(v[c].first<=rest)res=rec(c-1,rest-v[c].first)+v[c].second;
	res=max(res,rec(c-1,rest));
	return res;
}

class FibonacciKnapsack {
	public:
	long long maximalCost(vector <string> items, string C) 
	{
		int n=items.size();
		v.clear(); sum.clear();
		rep(i,n){
			stringstream ss(items[i]);
			ll a,b; ss>>a>>b;
			v.pb(mp(a,b));
		}
		sort(all(v));
		ll a=0, b=0;
		rep(i,n){
			a+=v[i].first; b+=v[i].second;
			sum.pb(mp(a,b));
		}
		rep(i,n)dp[i].clear();
		return rec(n-1,atoll(C.c_str()));
	}
};