01分数规划

经典例题：POJ2976

给定 /(n/) 个物品的价值 /(a/) 和 花费 /(b/) ，取其中的 /(k/) 个物品，求 /(/sum a[i] / /sum b[i]/) 的最大值。

题解：

假设 /(/sum a[i] / /sum b[i] = x/) ,则：

当 /(x/) 不是最优解时，/(/sum a[i] / /sum b[i] /ge x/) 成立，则存在一种组合使 /(/sum(a[i]-x/times b[i]) > 0/) 成立

为了尽可能让解更大，我们需要尽可能使该式成立，这样就可以继续找更大的解。

为了尽可能使该式成立，我们需要取最大的 /(k/) 个 /((a[i]-x/times b[i])/) ，

若 /(/sum(a[i]-x/times b[i]) > 0/) 成立， /(x/) 就不是最优解 ；

也就是说不断二分 /(x/) 的值，就可以找到最优解：

设 /(cheknum=/sum(a[i]-x/times b[i])/) ,

若 /(cheknum > 0/) , 则 /(x/) 可以更大

若 /(cheknum=0/) , 则 /(x/) 是最优解

若 /(cheknum<0/) , 则 /(x/) 需要更小

代码：

bool chek(int x)
{
    rep(i,1,n) c[i]=a[i]-x*b[i];
    sort(c+1,c+n+1,cmp);//从大到小
    int res=0;
    rep(i,1,k) res+=c[i];
    return res >= 0;
    
}

void solv()
{
    int l=0,r=maxx;
    while(r - l > eps)
    {
        double mid = (r+l)/2;
        if(chek(mid)) l=mid;//更大
        else r=mid;//变小
    }
    printf("%lf",l);
}