01分数规划

基本题型

01分数规划是这样的一类问题，有一堆物品，每一个物品有一个收益ai，一个代价bi，我们要求一个方案使选择的

\[\sum_{} a[i] / \sum_{} b[i] \]

最大(或最小)

分析

以最大为例，设x为最大值即x = Σai/Σbi，就有x * Σbi = Σai ---> Σai - x * Σbi = 0;
仔细分析，枚举可以被二分替代：x大了上式小于0，小了则大于0；

inline void solve(double x){
    for(rint i=1;i<=n;i++) d[i]=a[i]-b[i]*x;
    stable_sort(d+1,d+n+1);
    double ans=0;
    for(rint i=1;i<=n;i++) ans+=d[i]; 
        return ans;
}
int main(){
        ...............
    int gg=20;
    while(gg--)
    {
        double mid=(l+r)/2;
        double kk=solve(mid);
        if(kk>=0) l=mid;
        else r=mid; 
    } 
}

最优比率（例）生成树

概念

有带权图G, 对于图中每条边e[i], 都有benifit[i] (收入)和cost[i] (花费), 我们要求的是一棵生成树T, 它使得 ∑(benifit[i]) / ∑(cost[i]), i∈T 最大(或最小).

分析

设x[i]等于1或0, 表示边e[i]是否属于生成树.

则我们所求的比率 \(r = ∑(benifit[i]\)\(\times\)$x[i]) / ∑(cost[i] \[\times\] x[i]), 0 ≤ i < m $ .为了使 r 最大, 设计一个子问题 ---> 让 z = ∑(benifit[i]\[\times\]x[i]) - l \[\times\] ∑(cost[i]\[\times\]x[i]) = ∑(d[i]\[\times\]x[i]) 最大 (d[i] = benifit[i] - l * cost[i]) , 并记为z(l). 我们可以把z(l)看做以d为边权的最大生成树的总权值.

然后明确两个性质:

　1. z单调递减

　　证明: 因为cost为正数, 所以z随l的减小而增大.

　2. z( max(r) ) = 0

　　证明: 若z( max(r) ) < 0, ∑(benifit[i]\[\times\]x[i]) - max(r)\[\times\] ∑(cost[i]\[\times\]x[i]) < 0, 可化为 max(r) < max(r). 矛盾;
若z( max(r) ) >= 0, 根据性质1, 当z = 0 时r最大.

01分数规划

原文：https://www.cnblogs.com/Thomastine/p/11729537.html