平均値の最大化---二分検索

n個の品物の重量と価値はそれぞれw[i]とv[i]であり、その中からK個の品物を選んで単位重量の価値を最大にした.
1<=k<=n<=10^4
1<=w[i],v[i]<=10^6
一般的に考えられているのは単位価値で品物を並べ替えて、貪欲に選択することですが、この方法は間違っていて、サンプルに満足していません.私たちは一般的に2点検索で行います(実はこれは01点計画です)
定義:
条件C(x):=k個の物品を選択して、単位重量の価値がxより小さくないようにすることができる.
従って,原問題は条件C(x)を満たす最大xを解くことに変換される.では、C(x)が満足しているかどうかをどう判断しますか?
変形:(sigma(v[i])/sigma(w[i])>=x(iは私たちが選択したアイテムの集合Sに属する)
さらに、sigma(v[i]-x*w[i])>=0
そこで、条件が満たすのは、選択最大のk個と0以下である.そこでソート貪欲選択は判断でき,毎回判断の複雑さはO(nlogn)である.
コード:
 

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn=1e4;
const double eps=1e-5;
int w[maxn],v[maxn],n,k;
double y[maxn];
bool check(double r)
{
	for(int i=0;i<n;i++){
		y[i]=v[i]-r*w[i];
	}
	sort(y,y+n);
	reverse(y,y+n);
	double sum=0;
	for(int i=0;i<k;i++)
	{
		sum+=y[i];
	}
	return sum>=0;
} 
int main()
{
	while(cin>>n)
	{
		cin>>k;
		for(int i=0;i<n;i++)
			cin>>w[i]>>v[i];
		double lb=0,ub=1e6;
		while(ub-lb>eps)
		{
			double mid=(lb+ub)/2;
			if(check(mid)) lb=mid;
			else ub=mid;
		}
		printf("%.2f
",ub);	 
	}
	return 0;
}

テストのセットを指定します.
 
3
2
2 2
5 3
2 1
出力:0.75