[POJ 2976]Dropping tests(0-1分数规划)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <cmath>

#define MAXN 1010
#define EPS (1e-6)
#define INF 0x3f3f3f3f

using namespace std;

double w[MAXN],v[MAXN];
int n,k;
double value[MAXN];

bool check(double x) //推断平均值x是否可取
{
	double sum=0;
	for(int i=1;i<=n;i++)
		value[i]=v[i]-x*w[i];
	sort(value+1,value+n+1); //贪心排序，从大到小选取k个value[i]，且这k个value的和必须不小于0
	for(int i=n;i>=n-k+1;i--)
		sum+=value[i];
	return sum>=0;
}

int main()
{
	while(scanf("%d%d",&n,&k)!=EOF&&!(n==0&&k==0))
	{
	    k=n-k;
		for(int i=1;i<=n;i++)
			scanf("%lf",&v[i]);
		for(int i=1;i<=n;i++)
			scanf("%lf",&w[i]);
		double lowerBound=0,upperBound=INF; //二分这个平均值
		while(fabs(upperBound-lowerBound)>EPS)
		{
			double mid=(lowerBound+upperBound)/2;
			if(check(mid)) lowerBound=mid;
			else upperBound=mid;
		}
		printf("%.f\n",100*upperBound);
	}
	return 0;
}