分数规划

分数规划的一般形式：

Minimize/maximize

（以下讨论是求最大化函数）

原式变形得：

λ=a(x)/b(x)

λb(x)=a(x)

a(x)-λb(x)=0

根据上面的形式构建一个新函数：

g(λ)=max{a(x)-λb(x)}(x∈S)

定理1：

g(λ)有严格的单调性，对于λ1<λ2，有g（λ1）>g（λ2）。

证明：

设x2最大化了g（λ2），则：

g（λ2）=max{a(x)-λ2b(x)}(x∈S)

=a(x2)-λ2b(x2)

<a(x2)-λ1b(x2)

<=max{a(x)-λ1b(x)}(x∈S)=g（λ1）

即g（λ1）>=a(x2)-λ1b(x2)>g（λ2）

所以g（λ1）>g（λ2）。

定理2（Dinkelbach定理）：

设λ*为最优解，当且仅当λ=λ*，时g（λ）=0。

由定理1和定理2得出以下推论：

g（λ）=0等价于λ=λ*

g（λ）<0等价于λ>λ*

g（λ）>0等价于λ<λ*

因此可以将问题化简，二分答案。因为g（λ）不是分式函数，比较容易计算。时间复杂度为二分答案的复杂度*求函数g（λ）的复杂度。

分数规划的特例：01分数规划

Minimize/maximize

具体的实现方法：

(1)二分法：

doublel=...,r=...;

While(dblcmp(l-r)<=0)

{

Doublemid=(l+r)/2.0;

For(inti=1;i<=x;i++)G=min/max(G,A[i]-mid*B[i])

Ifdblcmp(G)>0l=mid+1e-6;elser=mid-1e-6;

}

Dinkelbach法

L=随便什么东西;

While(dblcmp(abs(L-ans))>1e-6)

{

Ans=L;

For(inti=1;i<=x;i++)G=min/max(G,A[i]-L*B[i]);

DBp=0.0,q=0.0;

Fori=每一个元素ifi在解中{p+=A[i];q+=B[i];}

L=p/q;

}

个人感觉Dinkelbach法快很多，但是要记多一点东西，总之要适应题目要求。

实践：

一、根据定义的直接应用

例题poj2976

给定A数组B数组，从中选择N-K个使得∑ai/∑bi最大

普通的01分数规划。二分答案，求出N个ai-λbi（1<=i<=N)，排序，选出最大的N-K就是得出的g（λ）。

当然也可以选择Dinkelbach法，速度比较快。

如果是求至少选N-K个，肯定是排序后选N-K个，多选不如少选。

二分法见【附1】

Dinkelbach法见【附2】

最优比例生成树

模型：

给一个无向图，每条边有两个权值ai,bi，求一棵生成树，使得用的边的∑ai/∑bi最小/最大。（以下讨论求最小）

解：二分答案mid，将每条边的权值变成ai-mid*bi，然后求最小生成树。设得出的答案是S，如果S>0，那么l=mid;否则r=mid。

当然也可以用Dinkelbach法。

例题：

poj2728

这题是比较裸最优比例生成树。

注意这题是稠密图，还是完全图，求生成树最好还是用Prim。

Dinkelbach法见【附3】

最优比例环

模型：

给定一个有向图，每条边有一个两个权值ai和bi，求一个环，使得∑ai/∑bi最小/最大。（以下讨论求最大）

二分答案mid，每条边的权值变成ai-mid*bi，然后用SPFA判断这个图中是否存在正环。如果是，那么l=mid;否则r=mid。

因为这类题只需要求是否存在正环，不需要求权值最大的环，所以用Dinkelbach法反而会更麻烦。

例题：

poj3621

给定一个有向图，每个点有一个权限Fi，每条边有一个权值Ti，求一个环，使得∑Fi/∑Ti最大。如果重复经过某个点，那么这个点的Fi只算一次；但是重复经过某条边，那么这条边的Ti要算多次。

本来想对于每一条有向边（ui，vi），将它的两个权值记为F[vi]和Ti，然后就直接套用01规划的做法。但是又怕出现环套环的情况（如下图的蓝色线），那么重合部分的点的Fi就算

了多次了。

内容需要下载文档才能查看

但是后来发现环套换情况可能成为最优解。证明如下：

假设环套环的情况（即上面蓝色线的情况）是最优解。

设大环的F值的和为x1，T值的和为y1；小环的F值的和为x2，T值的和为y2；重合部分的F值的和为x3，T值的和为y3。

易知环套环的情况（即上面蓝色线的情况）的F值的和为x1+x2-x3，T值的和y1+y2。环套环情况的解是(x1+x2-x3)/(y1+y2)

因为环套环情况的解是最优解，所以其必优于大环的解

x1/y1<(x1+x2-x3)/(y1+y2)

又因为(x1+x2-x3)/(y1+y2)<(x1+x2)/(y1+y2)

所以x1/y1<(x1+x2)/(y1+y2)

变形得x1y1+x1y2<x1y1+x2y1

x1y2<x2y1

x1y2+x2y2<x2y1+x2y2

(x1+x2)y2<x2(y1+y2)

(x1+x2)/(y1+y2)<x2/y2

又因为(x1+x2-x3)/(y1+y2)<(x1+x2)/(y1+y2)

所以(x1+x2-x3)/(y1+y2)<x2/y2

x2/y2就是小环的解，而小环的解竟然优于最优解环套环的情况，这与假设矛盾，因此环套环情况不可能是最优解。

证毕。

这道题真的非常巧妙，看的人一看就知道是01规划，但是又不能证明，这启示我们一个不等式关系：如果x1/y1<(x1+x2)/(y1+y2)，那么x2/y2>(x1+x2)/(y1+y2).

参考程序见【附4】

四、最大权闭合图，最大密度子图

参考我的博文《网络流——最小割》。

【参考资料】

《最小割模型在信息学竞赛中的应用》胡伯涛

http://wendang.chazidian.com/hhaile/article/details/8883652

【附1】

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<string>

#include<utility>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<set>

#include<map>

#include<iostream>

#include<bitset>

usingnamespacestd;

typedef

typedef

typedef

typedef

typedef

#define

#define

#define

#define

#define

#define

#define

#define

#definelonglongLL;unsignedlonglongULL;doubleDB;pair<int,int>PII;map<string,int>MSI;mmst(a,v)memset(a,v,sizeof(a))mmcy(a,b)memcpy(a,b,sizeof(a))re(i,a,b)for(inti=a;i<=b;i++)red(i,a,b)for(inti=a;i>=b;i--)fifirstsesecondbit(a,b)((a>>b)&1)power2(a)(1<<a)power2LL(a)(1LL<<a)

T>inline

T>inline

T>inline

T>inlineTsqr(Tx){returnTAbs(Tx){returnvoidUpMax(T&t,TvoidUpMin(T&t,Tx*x;}(x>=0)?x:-x;}tmp){if(t<tmp)t=tmp;}tmp){if(t>tmp)t=tmp;}template<classtemplate<classtemplate<classtemplate<class