01 分数规划 poj 2976 利用二分法即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn = 1005;
double a[maxn],b[maxn],c[maxn];
int m,n,k;
double L,R,mid;

bool big(double p){
    for(int i=0;i<n;i++) c[i] = a[i] - p * b[i];
    sort(c,c+n);
    double sum = 0;
    for(int i=n-1;i>n-1-m;i--) sum += c[i];
    if(sum >= 0) return true;
    else         return false;
}
int main()
{
    //if(freopen("input.txt","r",stdin)== NULL)  {printf("Error\n"); exit(0);}
    while(cin>>n>>k && n){
        m = n - k; 
        L = 0.0;
        R = 1.0;
        for(int i=0;i<n;i++) cin>>a[i];
        for(int i=0;i<n;i++) cin>>b[i];
        while(R - L > 1e-5){
            mid = (L + R)/2; //printf("%.2lf\n",mid);
            if(big(mid)){
                L = mid;  
            }
            else 
                R = mid; //printf("mid%d  R%.2lf\n",mid,R);
               
        }
        int ans =  floor(100 * L+0.5);
        printf("%d\n",ans);
    }
    return 0;
}