一个简单的算法,0/1分数规划.具体就是二分.

分子是一些ai的和,分母是一些bi的和.假定我的值是满足要求且要扩大.那我们很容易得出ai-bi*x>=0.
那么就是我们按ai-bi*x排个序,删掉k个小的即可.
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
const double eps=1e-5;
int n,k;
double a[N],b[N],c[N];
bool ck(double x)
{
    for(int i=1;i<=n;i++)
    {
        c[i]=a[i]-b[i]*x;
    }
    sort(c+1,c+1+n);
    double sum=0.0;
    for(int i=k+1;i<=n;i++)
    {
        sum+=c[i];
    }
    if(sum>=0.0) return true;
    else        return false;
}

int main()
{
    while(cin>>n>>k)
    {
        if(n==0&&k==0)  break;
        for(int i=1;i<=n;i++)   cin>>a[i];
        for(int i=1;i<=n;i++)   cin>>b[i];
        double l=0.0,r=100.0;
        while(r-l>=eps)
        {
            double mid=(r+l)/2.0;
            if(ck(mid))
            {
                l=mid;
            }
            else
            {
                r=mid;
            }
        }
        cout<<(int)(100*l+0.5)<<endl;
    }
    return 0;
}