yukicoder : No.626 Randomized 01 Knapsack

割と苦戦した記憶が。
https://yukicoder.me/problems/no/626

問題

荷物の価値・重みが与えられるので、重みの総和の上限を超えない範囲で荷物の価値の総和を最大化する典型的なナップサック問題である。
ただし、価値・重みは一様な乱数で指定される。

解法

まず荷物を価値/重みの大きい順にソートしておき、価値の総和を高めやすい方からどん欲に利用していくことを考える。
荷物を1つずつ加える・加えないを判定していく際、
f(n) := 先頭n個の荷物をナップサックに入れる・入れないを考えた際、(価値の総和,重みの総和)を価値・重みの総和がいずれも大きい順に並べた数列
を更新していくと通った。

ただ、これが「価値・重みは一様な乱数で指定される。」の条件がない場合にも通るかは未確認。

int N;
ll W;
pair<ll,ll> P[5050];
ll ma=0;

bool cmp(pair<ll,ll> L,pair<ll,ll> R) {
	return L.first*1.0/L.second>R.first*1.0/R.second;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>W;
	FOR(i,N) {
		cin>>P[i].first>>P[i].second;
	}
	sort(P,P+N,cmp);
	
	vector<pair<ll,ll>> V;
	V.push_back({0,0});
	FOR(i,N) {
		ll v=P[i].first,w=P[i].second;
		vector<pair<ll,ll>> V2=V;
		FORR(vv,V) if(vv.second+w<=W) V2.push_back({vv.first+v,vv.second+w});
		V.clear();
		sort(ALL(V2));
		reverse(ALL(V2));
		ll pre=W+1;
		FORR(vv,V2) if(vv.second<pre) V.push_back(vv), pre=vv.second;
	}
	
	ll ma=0;
	FORR(v,V) ma=max(ma,v.first);
	
	
	cout<<ma<<endl;
	
	
}

まとめ

こういうのの計算量、どう見積もればいいんだろ。