基本0--1 分数规划题 poj -- 2976

题意:
给定n个二元数,选取n-k个二元组合,使得sigma(a[i])/sigma(b[i])最大.
思路:
所以这就是最裸的0-1分数规划题,直接上模板,注意读入时不要用cin,应该用scanf,否则会超时,我也不知道呀.

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<functional>
#include<vector>
#include<stack>
#include<map>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
#define mod 1000000007
using namespace std;
const int maxn=1e6;
const db eps=1e-7;
const int inf=1e9;
const ll INF=1e15;
db a[1005],b[1005],c[1005];
int main()
{
    int n,k;
    while(scanf("%d %d",&n,&k)!=EOF){
        CLR(c);
        if(n==0 && k==0)
            break;
        for(int i=0;i<n;i++)
            scanf("%lf",&a[i]);
        for(int i=0;i<n;i++)
            scanf("%lf",&b[i]);

        db l=0.0;
        db r=10.0;   //二分的范围你可以试着确定,根据题意来.这里题目中时保证了分母比分子大,
                     //所以答案应该时不会超过1的.（当然大点也行）
        db mid;
        while(r-l>eps){
            mid = (r+l)/2.0;
            /*cout << l << " " << r << endl;
            cout << mid << endl;*/
            for(int i=0;i<n;i++)
                c[i]= a[i]-mid*b[i];
            sort(c,c+n);
            db sum=0;
            for(int i=k;i<n;i++)
                sum+=c[i];

            if(sum > 0)   //目的是使sum不断逼近0.所以大于0时就要减小sum,故L右移,就可以把
                          //sum减小.因为根据推论,当sum越接近0时,答案越最优.
                l=mid;
            else
                r=mid;
        }
        printf("%.0f\n",mid*100);
    }
}
/*
3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0
*/