01分数规划

定义：

分数规划用来求一个分式的极值，形象一点的说就是给出 $a_i$ 和 $b_i$ ，让我们求一组wi属于{0,1}的最小化或者最大化 $\sum_{i=1}^{n}\frac{a_i\times w_i}{b_i\times w_i}$ ,另外一种描述就是每种物品有两个权值a和b，选出若干个物品使得 $\sum_\ \frac{a}{b}$ 最小/最大，而且对于一些比较特殊的题目会出现特殊的限制比如分子或者分母要求一定数量的物品等等。

求解：

方法一：二分

假设我们这里需要求一个最大值，我们二分一个答案mid，带入式子 $\sum_{i=1}^{n}\frac{a_i\times w_i}{b_i\times w_i}>mid$ ==> $\sum_{i=1}^{n}\ {a_i}\times {w_i}>\sum_{i=1}^{n}\ b_i\times w_i\times mid$ ==> $\sum_{i=1}^{n}w_i\times (a_i-mid\times b_i)>0$ 那么我们只要求出不等号左边的式子的最大值即可，如果最大值比0要大，说明mid可行，否则不可行。

假设我们这里需要求一个最小值，我们二分一个答案mid，带入式子 $\sum_{i=1}^{n}\frac{a_i\times w_i}{b_i\times w_i}<mid$ ==> $\sum_{i=1}^{n}\ {a_i}\times {w_i}<\sum_{i=1}^{n}\ b_i\times w_i\times mid$ ==> $\sum_{i=1}^{n}w_i\times (a_i-mid\times b_i)<0$ 那么我们只要求出不等号左边的式子的最小值即可，如果最小值比0要小，说明mid可行，否则不可行。

方法二：Dinkelbach算法

这个算法其实就是以二分函数图像的单调性为原理，利用了check中计算得出的结果，通过改变二分枚举的中间点在图像上的位置来优化二分。

我们可以根据几张图来演示如何快速找到答案：

alt

图中的红点是答案，紫线是我们的mid（我们直接二分了一个中点）从这个点开始每次取这个点与曲线的交点以那个交点为基准做一个切线 alt

接着我们将开始的mid的切线与x轴交点的x坐标作为新的x坐标，不断重复知道找到答案即可。

这个算法的效果却不见的有多么优秀，因为二分的函数图像有可能是坑坑洼洼的，所以有时这个算法跑数据的时间反而比二分大，但是如果图像是较为光滑的弧线，或许Dinkelbach* 算法就能充分展现它的优势了。

另外这个算法复杂度就是 O(O(玄学)) 的，出题人一般不会卡（想卡也难卡，因为初始点可以是任意的，这就相当于随机算法了啊！鬼知道你乱搞出来的初始点会不会就是答案了），但是讲道理，这个算法效率确实没有保障...

这里我也不过多赘述，因为我也不太会使用，知道大致思路即可，主要是二分的方法熟练掌握即可。

实例：

模板：

题意：有 n个物品，每个物品有两个权值a和b。让我们求一组wi属于{0,1}，最大化 $\sum_{i=1}^{n}\frac{a_i\times w_i}{b_i\times w_i}$ 的值。

思路：根据上面的式子二分求解： $\sum_{i=1}^{n}w_i\times (a_i-mid\times b_i)>0$ 每次将 $a_i-mid\times b_i$ 作为第i个物品的权值，然后我们贪心的想将所有权值>0的部分拿走就可以将答案最大化。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define inf 1e18
void cb(){
    int n;cin>>n;
    vector<int>a(n+1),b(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    double l=0,r=inf;
    auto check=[&](double x)->int{
        double s=0;
        for(int i=1;i<=n;i++){
            if(a[i]-x*b[i]>0)s+=a[i]-x*b[i];
        }
        return s>0;
    };
    while(r-l>1e-9){
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    cout<<fixed<<setprecision(10)<<l<<'\n';
} 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int _;_=1;
    while(_--)cb();
    return 0;
}

分数规划的有机结合

1.不与任何算法相结合的裸题

P10505 Dropping TestP10505 Dropping Test - 洛谷 | 计算机科学教育新生态

题意：

就是让我们求 $100\times \frac{\sum_{i=1}^{n-k}a_i}{\sum_{i=1}^{n-k}b_i}(k\subset {(1,n)})$ 的最大值

思路：

上面我们就讲过二分求分数划分的最大值： $\sum_{i=1}^{n}w_i\times (a_i-mid\times b_i)>0$ 那么我们只要求出不等号左边的式子的最大值即可，如果最大值比0要大，说明mid可行，否则不可行。也可以将每个科目的权值设为 ${a_i-mid\times b_i}$ 每次二分的时候我们对总科目从大到小排序取前n-k个数保证总和>0，最后求出最大值即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define inf 1e18
void cb(){
    while(1){
        int n,k;cin>>n>>k;
        if(!n&&!k)break;
        vector<int>a(n+1),b(n+1);
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        double l=0,r=inf;
        auto check=[&](double x)->bool{
            double s=0;
            vector<double>d(n+1);
            for(int i=1;i<=n;i++)d[i]=a[i]-x*b[i];
            sort(d.begin()+1,d.end(),[&](double x,double y){
                return x>y;
            });
            for(int i=1;i<=n-k;i++)s+=d[i];
            return s>0;
        };
        while(r-l>1e-9){
            double mid=(l+r)/2;
            if(check(mid))l=mid;
            else r=mid;
        }
        cout<<fixed<<setprecision(0)<<l*100.0<<'\n';
    }
} 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int _;_=1;
    while(_--)cb();
    return 0;
}

2.与01背包相结合（最优比率背包）

P4377 [USACO18OPEN] Talent Show G[P4377 USACO18OPEN] Talent Show G - 洛谷 | 计算机科学教育新生态

题意：

求 $1000\times\sum_{i=1}^{n}\frac{a_i\times w_i}{b_i\times w_i}(\sum_{i=1}^{n}b_i\times w_i>=w)$ 的最大值

思路：

在板子的基础之上多了一个限制，分母至少>=W,这个时候我们无法使用贪心的想法，我们可以考虑01背包的解法，把 ${b_i}$ 作为第i个物品的重量， ${a_i-mid\times{b_i}}$ 作为第i个为物品的价值，然后就可以将问题转化成了背包，最大值就是dp[n,w]，二分的时候保证dp[n,w]>0不断更换边界这样就可以求出最大值了记得01背包的时候对于大于w的区域我们都将这些归结在w身上即可。

代码：

这个题解也不错https://www.luogu.com.cn/article/zkbgf8st
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define inf 1e18
int dp[1100];
void cb(){
    int n,w,sum=0;cin>>n>>w;
    vector<int>a(n+1),b(n+1);
    for(int i=1;i<=n;i++)cin>>b[i]>>a[i],a[i]*=1000,sum+=a[i];//直接乘上1000防止小数出现产生误差
    int l=0,r=sum;
    auto check=[&](int x)->bool{
        memset(dp,0x80,sizeof dp);//因为价值可能为负数所以直接赋值成负无穷
        dp[0]=0;
        for(int i=1;i<=n;i++){
            for(int j=w;j>=0;j--){
                int k=min(w,b[i]+j);//将多的部分全部累积到w上
                dp[k]=max(dp[k],dp[j]+a[i]-x*b[i]);
            }
        }
        return dp[w]>=0;
    };
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))l=mid+1;
        else r=mid;
    }
    cout<<l-1<<'\n';
} 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int _;_=1;
    while(_--)cb();
    return 0;
}
//小数做法 https://www.luogu.com.cn/record/195955190

。。。。还在学习中（与生成树结合，即最优比率生成树、与负环判定结合，即最优比率环、与网络流结合，即最大密度子图。。。）会在不久后持续更新，请谅解！