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

解法

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

\dfrac{\sum a_i \times x_i}{\sum b_i \times x_i} \\

其中

x_{i} \in \{0,1\}

。

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

ans

，即

\dfrac{\sum a_i \times x_i}{\sum b_i \times x_i} \leq ans

把分母消掉后移项得到

\sum a_i \times x_i - ans \times \sum b_i \times x_i \leq 0

可

ans

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

但这样是有问题的。因为我们希望

ans

最大，而枚举的 $mid$ 肯定 $\leq$ 最终的 $ans$ ，也就是说， $\dfrac{\sum a_i \times x_i}{\sum b_i \times x_i}$ 应该是 $\geq ans$ 的！

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

\sum a_i \times x_i - ans \times \sum b_i \times x_i \geq 0

基础分数规划

例题：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

就行了。注意因为是分式，所以使用浮点数二分。

给出代码：

CPP

12345678910111213141516171819202122232425262728293031323334353637#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

中。

给出代码：

CPP

#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

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

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

\dfrac{\sum F_i}{\sum T_i}

的值最大。

那么很显然还是要用分数规划。依旧把

a_i-mid \times b_i

作为边权（注意

a_i

是点权），那么权值最小的环就是最小值。因为要判断最小值是否

\leq 0

，所以判断负环即可。这里使用 SPFA 判环。当然如果你想用更快的 dfs 判环也没问题。

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

给出代码：

CPP

#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 判环。

总结

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

浅谈分数规划

文章操作

解法

基础分数规划

分数规划结合 01 背包

分数规划结合最小生成树

分数规划结合判环

总结

相关推荐

评论

浅谈分数规划