poj2976 Dropping tests（01分数规划）

题目链接

分析：
01分数规划

简单说一下吧：
最大化： ∑a[i]∗x[i]∑b[i]∗x[i] $\frac{\sum a[i]\ast x[i]}{\sum b[i]\ast x[i]}$
设 F(L)=∑a[i]∗x[i]−L∗∑b[i]∗x[i]=∑(a[i]−L∗b[i])∗x[i] $F(L)=\sum a[i]\ast x[i]-L\ast \sum b[i]\ast x[i]=\sum (a[i]-L\ast b[i])\ast x[i]$
如果 F(L) $F(L)$的值>0，说明存在一个大于L的可行答案
所以我们二分L即可

对于这道题来说，是在简单01分数规划的基础上加了数量限制(n-k)
设 c[i]=a[i]−L∗b[i] $c[i]=a[i]-L\ast b[i]$，将 c $c$从大到小排序，取前 (n−k) $(n-k)$大，判断与0的关系即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const double eps=1e-6;
const int N=1005;
int n,m;
double a[N],b[N],c[N];

int cmp(double x,double y) {return x>y;}

int check(double L) {
    for (int i=1;i<=n;i++)
        c[i]=a[i]-L*b[i];
    sort(c+1,c+1+n,cmp);
    double x=0;
    for (int i=1;i<=n-m;i++)
        x+=c[i];
    return x>=0;
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF&&n+m) 
    {
        for (int i=1;i<=n;i++) scanf("%lf",&a[i]);
        for (int i=1;i<=n;i++) scanf("%lf",&b[i]);

        double l=0,r=0,ans=0;
        for (int i=1;i<=n;i++) r=max(r,a[i]/b[i]);
        while (r-l>=eps) {
            double mid=(l+r)/2;
            if (check(mid)) ans=max(ans,mid),l=mid;
            else r=mid;
        }
        printf("%.0lf\n",ans*100);
    }
    return 0;
}