浅谈分数规划

Otachi · 2025-09-20 13:16:26 · 算法·理论

这个算是一个非常冷门的知识点了，洛谷上只有一篇文章讲了分数规划，但是个人认为对式子的推导不是那么详细，于是自己写了一篇。

解法

二分法是分数规划最常用的方法。分数规划简单来说，就是求形如下面分式的极值

其中 x_{i} \in \{0,1\}。

下面的推导统一以求最大值为例。设最大值为 ans，即

把分母消掉后移项得到

可 ans 就是我们要求的啊！很简单，二分一下就行了。

但这样是有问题的。因为我们希望 ans 最大，而枚举的 mid 肯定 \leq 最终的 ans，也就是说，\dfrac{\sum a_i \times x_i}{\sum b_i \times x_i} 应该是 \geq ans 的！

所以，最后推导出的式子应该是

基础分数规划

例题：P1570 KC 喝咖啡

根据上面的式子，要使 \sum a_i \times x_i - ans \times \sum b_i \times x_i \geq 0，而且要使 x_i=1 的个数 =m。不难想到每次 check(mid) 时令 c_i=a_i-mid \times b_i，然后根据 c_i 从大到小排序，然后判断 \sum_{i=1}^m c_i \geq 0 就行了。注意因为是分式，所以使用浮点数二分。

给出代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=205;
int n,m;
int a[N],b[N];
double c[N];
bool cmp(double x,double y)
{
    return x>y;
}
bool check(double mid)
{
    for(int i=1;i<=n;i++)
        c[i]=a[i]-mid*b[i];
    sort(c+1,c+n+1,cmp);
    double sum=0;
    for(int i=1;i<=m;i++)
        sum+=c[i];
    return sum>=0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    double l=0,r=2e6,mid;
    while(r-l>1e-5)
    {
        mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    printf("%.3lf\n",l);
    return 0;
}

分数规划结合 01 背包

例题：P4377 [USACO18OPEN] Talent Show G

这道题和板子差不多，但是多了分母 \geq W 的限制。这就不太好贪心了，怎么办？

令 dp_{j} 为总质量为 j 时 a_i-mid \times b_i 的最大值，其中若总质量 \geq W 则算在 dp_W 中。

给出代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=255;
int n,W;
int a[N],b[N];
double dp[1005];
bool check(double mid)
{
    for(int i=1;i<=W;i++)
        dp[i]=-2e9;
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=W;j>=0;j--)
        {
            int k=min(j+a[i],W);
            dp[k]=max(dp[k],dp[j]+(b[i]-mid*a[i]));
        }
    return dp[W]>=0;
}
int main()
{
    scanf("%d%d",&n,&W);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);
    double l=0,r=1e6,mid;
    while(r-l>1e-5)
    {
        mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    printf("%d\n",int(floor(1000*l)));
    return 0;
}

分数规划结合最小生成树

例题：Desert King

看到“他只需要建必要的水渠，确保所有村庄都能接上水，也就是说，每个村庄到首都只有唯一一条通路。”这句话，就说明要用最小生成树了。又要求比值，就可以把 b_i-a_i \times mid 作为边权，跑最小生成树即可。

代码就不给了，非常简单。

分数规划结合判环

例题：P2868 [USACO07DEC] Sightseeing Cows G

看到题目颜色不要怕，因为这个题目一开始的时候有很大的震撼力，之后同类型甚至更难的题目也只有蓝了。

题目大致意思就是，要求你给出一个环，使

的值最大。

那么很显然还是要用分数规划。依旧把 a_i-mid \times b_i 作为边权（注意 a_i 是点权），那么权值最小的环就是最小值。因为要判断最小值是否 \leq 0，所以判断负环即可。这里使用 SPFA 判环。当然如果你想用更快的 dfs 判环也没问题。

注意题目没说是一个完全图，所以要建一个超级源点。

给出代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1005;
int n,m;
int a[N];
double dis[N];
int cnt[N];
bool vis[N];
vector<pii>g[N];
bool SPFA(double mid)
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        q.push(i);
        vis[i]=true;
        dis[i]=a[i];
        cnt[i]=1;
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(pii i:g[u])
        {
            int v=i.first,w=i.second;
            if(dis[v]<dis[u]-w*mid+a[v])
            {
                dis[v]=dis[u]-w*mid+a[v];
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=true;
                    cnt[v]++;
                    if(cnt[v]>=n)return true;
                }
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u].push_back({v,w});
    }
    double l=0,r=1e6,mid,ans=0;
    while(r-l>1e-5)
    {
        mid=(l+r)/2;
        if(SPFA(mid))
        {
            ans=mid;
            l=mid;
        }
        else
            r=mid;
    }
    printf("%.2lf\n",ans);
    return 0;
}

习题：P1768 天路

这道题和上一道题差不多，但是一条边有两个边权，而且由于时间卡得比较紧，所以只能用 O(n) 的 dfs 判环。

总结

分数规划虽然考的比较少，但也是一种可以灵活结合其他算法的算法。