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())); } };