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);
}