浅谈分数规划

· · 个人记录

关于 SPFA，他死了。 关于分数规划，他还活着。 ——鲁迅

  1. 有用的分数规划模板。

由一个简单地问题引入。

有 2 个元素个数为 n 序列：a，b。让你求出一个满足 \forall s_i \in\{0,1\} 且长度为 n 的序列 s，满足：

\sum\limits^{n}_{i=1}s_i=k

使得:

x=\frac{\sum\limits^{n}_{i=1}s_ia_i}{\sum\limits^{n}_{i=1}s_ib_i}

中的 x 最大。

然后呢，题目问的就是这个最大的 x。

这个题目由于 s 序列只由 0 或 1 组成，又是要求一个最大的比值，因此这个算法又被称为 0/1 分数规划。

那么遇到这种问题要怎么做呢？

每个元素可以选或不选是吧，01 背包启动！

那么问题来了，假设我们知道了 \dfrac{a_i}{b_i}，也知道了 \dfrac{a_j}{b_j}，我们根本无从得知 \dfrac{a_i+a_j}{b_i+b_j}。01 背包的就是基于这种转移的，因此这题无法使用 01 背包来解决。

那么我们考虑使用二分查找。找到最大的 x，便是答案。大部分分数规划问题是基于二分查找方法实现的。

那么我们设：

\frac{\sum\limits^{n}_{i=1}s_ia_i}{\sum\limits^{n}_{i=1}s_ib_i}\ge x

移项得：

\sum\limits^{n}_{i=1}s_ia_i\ge x\sum\limits^{n}_{i=1}s_ib_i x\sum\limits^{n}_{i=1}s_ib_i\le \sum\limits^{n}_{i=1}s_ia_i \sum\limits^{n}_{i=1}s_ixb_i\le \sum\limits^{n}_{i=1}s_ia_i \sum\limits^{n}_{i=1}(s_ixb_i-s_ia_i)\le 0 \sum\limits^{n}_{i=1}s_i(xb_i-a_i)\le 0

设对于 \forall i，令 c_i=xb_i-a_i。

则：

\sum\limits^{n}_{i=1}s_ic_i\le 0

那么我们只要把 c 序列按升序排序，获取前 k 大的 c 值，然后相加的到和 sum，只需要判断是否有 sum \le 0，就可以知道当前 x 是否可行了。

参考代码：

#include<bits/stdc++.h>
using namespace std;
double a[2000],b[2000];
int n,k;
double l,r;
const double eps=1e-8;
bool check(double mid)
{
    double c[2000];
    for(int i=1;i<=n;i++)c[i]=mid*b[i]-a[i];
    sort(c+1,c+1+n);
    double sum=0;
    for(int i=1;i<=n;i++)sum+=c[i];
    return (sum<=0);
}
main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a[i],&b[i]);
        r+=a[i];
    }
    while(r-l>eps)
    {
        double mid=(l+r)/2.0;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.4lf",l);
    return 0;
}

上述问题中去除

\sum\limits^{n}_{i=1}s_i=k

这个条件的问题，也可以同类似的方法求解。而且甚至更加简单，如果对 c 序列排序之后这个序列的最小值都大于 0 的话，那么这个 x 值就不合法。这样 check 函数长这样：

bool check(double mid)
{
    double c[2000];
    for(int i=1;i<=n;i++)c[i]=mid*b[i]-a[i];
    double minn=1e9;
    for(int i=1;i<=n;i++)minn=min(minn,c[i]);
    return (minn<=0);
}

复杂度：O(n \log value)。

  1. 最优比例背包问题

【例题 1】洛谷 P4377 [USACO18OPEN] Talent Show G

首先来看为什么能从这个问题看出这是一道分数规划呢？原题语句：

帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

在原集合中选取一个子集，使得两个属性的比值最大，这便是分数规划的典型表达。这种问题，还添加了一个限制条件，那就是总重量之和不小于 W。我们会发现，这种问题和背包问题的限制非常的相似。由于它求得是一个最佳的比值，有和背包问题非常的相像，因此这类问题叫做最优比例背包。

还是用老方法进行分析，考虑二分查找一个 x，使：

\frac{\sum\limits^{n}_{i=1}s_it_i}{\sum\limits^{n}_{i=1}s_iw_i} \ge x,\text{且}\sum\limits^{n}_{i=1}s_iw_i\ge W,\forall s_i \in\{0,1\}

用同样的方法进行整理：

\sum\limits^{n}_{i=1}s_it_i\ge x\sum\limits^{n}_{i=1}s_iw_i \sum\limits^{n}_{i=1}s_i(t_i-xw_i) \ge 0

然后我们发现，每个奶牛的贡献就变成了 t_i-xw_i，和别的奶牛没有任何关系！！这样我们就满足了动态规划的无后效性。于是问题就转换为：第 i 个物品价值为 t_i-xw_i，重量为 w_i，要求装的东西重量大于 W，且背包所装物品价值之和最大！如果这个最大的值大于等于 0，说明这个 x 不可行。否则可行。

至于判断函数，选择使用刷表法进行 01 背包。具体实现思路为：

设 dp_i 表示重量为 i 时的最大价值，如果总重量大于等于 W 那么都存在 dp_W 里。使用滚动数组进行处理，然后进行 dp 后判断 dp_W 是否大于等于 0。代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,W,w[255],t[255];
double l,r,mid,y[255],dp[1002];
bool check(double x)
{
    for(int i=1;i<=n;i++)y[i]=t[i]-x*w[i];
    for(int i=0;i<=W;i++)dp[i]=-0x3f3f3f3f;
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=W;j>=0;j--)
            if(j+w[i]>=W)dp[W]=max(dp[W],dp[j]+y[i]);
            else dp[j+w[i]]=max(dp[j+w[i]],dp[j]+y[i]);
    return dp[W]>=0;
}
main()
{
    scanf("%d%d",&n,&W);
    for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&t[i]),r+=t[i];
    while(r-l>=0.00000001)
    {
        mid=(l+r)/2.0;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%d",(int)floor(mid*1000));
    return 0;

}
  1. 最优比例生成树

【例题 2】洛谷 P4951 [USACO01OPEN] Earthquake

还是使用基本一致的套路分析。原题语句：

请帮助奶牛们选择修复哪些道路，才能使单位时间的利润最大？

单位时间的利润，指的是收益除以时间的比值。它要保证所有牧场联通，那么要保证边数最少，那么就要保证这是图的一棵生成树。

设有序列 s(\forall s_i \in \{0,1\}) 中的元素 s_i 表示第 i 边要不要选，且所有选的边会构成一棵生成树。

设：

\text{总利润}C=f-\sum\limits^{n}_{i=1}s_ic_i \text{总时间}V=\sum\limits^{n}_{i=1}s_it_i

再设：

\dfrac{C}{V} \ge x \dfrac{f - \sum\limits^{n}_{i=1} s_ic_i}{\sum\limits^{n}_{i=1} s_it_i} \ge x

得：

f - \sum\limits^{n}_{i=1} s_ic_i\ge x\sum\limits^{n}_{i=1} s_it_i

移项：

f\ge x\sum\limits^{n}_{i=1} s_it_i + \sum\limits^{n}_{i=1} s_ic_i \sum\limits^{n}_{i=1} s_i(xt_i+c_i) \le f

那么我们就发现所有边中的第 i 条边的贡献是 xt_i+c_i，和任何别的边都没有任何关系！

于是，我们考虑建一个新图，新图每一条边两端的节点不变，第 i 条边的边权为 xt_i+c_i。然后跑一遍最小生成树，求出最小生成树中所有边的权值总和 sum。如果 sum \le f，那么这个 x 值合法。否则不合法。

具体实现如下：

#include<bits/stdc++.h>
#define int long long
#define N 402
#define M 11200
#define EPS 1e-10
using namespace std;
struct edge{int u,v;double c,t;}old[M];
struct Node{int u,v;double w;}e[M];
bool operator <(Node x,Node y){return x.w<y.w;}
int fath[N],n,m;
double f,l,r,mid;
void init()
{
    for(int i=1;i<=n;i++)fath[i]=i;
}
int find(int k)
{
    if(fath[k]==k)return k;
    else return find(fath[k]);
}
int un(int k1,int k2)
{
    fath[find(k1)]=find(k2);
}
double kruscal()
{
    init();
    sort(e+1,e+1+m);
    int cnt=0;
    double ret=0;
    for(int i=1;cnt<n-1;i++)
    {
        int nowu=e[i].u,nowv=e[i].v;
        if(find(nowu)==find(nowv))continue;
        un(nowu,nowv);
        ret+=e[i].w;
        cnt++;
    }
    return ret;
}
int check(double x)
{
    for(int i=1;i<=m;i++)e[i]=(Node){old[i].u,old[i].v,old[i].t*x+old[i].c};
    return kruscal()<=f;
}
main()
{
    scanf("%lld%lld%lf",&n,&m,&f);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld%lf%lf",&old[i].u,&old[i].v,&old[i].c,&old[i].t);
    r=0x3f3f3f3f;
    while(r-l>=EPS)
    {
        mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.4lf",l);
    return 0;
}
  1. 最优比例环

【例题 3】洛谷 P2868 [USACO07DEC] Sightseeing Cows G

这题稍微有点不一样。

这也是一道分数规划题，因为它求的是均值最小的环。

我们设 s 序列标记的是每一个点是否在这个环上，e'_i 表示第 i 个节点到这个环上下一个点的边的时间。

二分枚举出一个答案 x，

\dfrac{\sum\limits^{n}_{i=1}s_iF_i}{\sum\limits^{n}_{i=1}s_ie'_i} \ge x \sum\limits^{n}_{i=1}s_iF_i \ge x\sum\limits^{n}_{i=1}s_ie'_i \sum\limits^{n}_{i=1}s_i(F_i-xe'_i) \ge 0

因此，我们就转换成我们把原图的第 i 条边的权值转换为 F_i-xe'i，然后判断对于每一个 x，是否存在从任意一个节点出发的正边权环。那么我们比较难以完成判断。于是：

关于 spfa，他没死！！！！！

考虑把每一条边的权值取相反数，变成 F_i-xe'i。然后使用 spfa 判断负环就可以了。

#include<bits/stdc++.h>
#define N 11200
#define M 56000
using namespace std;
struct Node{int to,next;double w;}edge[M];
int cnt,head[N],ff[N],n,m,U[M],V[M],W[M];
int c[N],flag[N];
double d[N];
double l,r,mid;
void init()
{
    for(int i=0;i<N;i++)head[i]=-1;
    for(int i=0;i<M;i++)edge[i].next=-1;
    cnt=0;
}
int addedge(int u,int v,double w)
{
    edge[cnt]=(Node){v,head[u],w};
    head[u]=cnt++;
}
bool spfa(int s)
{
    for(int i=1;i<=n;i++)c[i]=flag[i]=0,d[i]=0x3f3f3f3f;
    queue<int> q;
    c[s]=1;
    d[s]=0;
    q.push(s);
    flag[s]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        flag[now]=0;
        for(int i=head[now];~i;i=edge[i].next)
        {
            int t=edge[i].to;double tw=edge[i].w;
            if(d[now]+tw<d[t])
            {
                d[t]=d[now]+tw;
                if(!flag[t])
                {
                    flag[t]=1;
                    if(c[t]>=n)return 1;
                    c[t]++;
                    q.push(t);
                }
            }
        }
    }
    return 0;
}
bool check(double x)
{
    init();
    for(int i=1;i<=m;i++)addedge(U[i],V[i],x*W[i]-ff[U[i]]);
    return spfa(1);
}
main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&ff[i]),r+=ff[i];
    for(int i=1;i<=m;i++)scanf("%d%d%d",&U[i],&V[i],&W[i]);
    for(int i=1;i<=30;i++)
    {
        mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.2f",l);
    return 0;
}

最后总结一下， 分数规划并不是一个具体的算法，而是一种思路，就和 dp 一样。分数规划的难点在于建模，列不等式，对思维的要求较高，而对代码能力只有一般要求。

本文选用的题目多为来自某一个遥远的国度的 USACO 题目，国内考得并不多，甚至不是 NOI 大纲的考试范围。但是，这是我们学习其他算法时能够借鉴的。