【学习笔记】01 分数规划

分数规划问题，大概就是一类求解分式最值的问题。

比如下面这个问题：给定 \(n\) 个物品，每个物品有两个属性 \(a\) 和 \(b\)，保证均为正数，从中选出若干个出来，要求最小化（也可能是最大） \(\frac{\sum a}{\sum b}\)。

当然还可能有一些奇怪的其他要求，比如限制分子分母大小之类的。

下文将会选几个最简单的此种类型题目进行分析。

二分求解

一般情况下，求解此类问题最常见的方法就是二分答案。

就一上面提到的问题举例，考虑去二分这个最小值，将其记为 \(mid\)，然后问题就转换成了判断最值能否小于等于 \(mid\)。如何判断呢？稍微推导一下（上文说过了都是正数，不用管不等号）：

这样问题就变得十分简单了，相当于对于每个物品将 \(a_i-mid\times b_i\) 作为新的属性，然后从中选出来若干个使得新属性之和不超过 \(0\)，具体解决方法就视情况而定了。

Dinkelbach 算法

嗯？这是个什么东西？问我？我也不知道。

确实没具体了解过，这里就先引用下 OI Wiki 上解释的：

Dinkelbach 算法的大概思想是每次用上一轮的答案当做新的 L 来输入，不断地迭代，直至答案收敛。

一些例题

尽量选了些有营养的，避免重复。

洛谷 P1570 KC 喝咖啡

题目链接

简要题意：有 \(n\) 个物品，每个物品有两个属性 \(v\) 和 \(c\)，从中选取 \(m\) 个，使得 \(\frac{\sum v}{\sum c}\) 最大。

入门题，考虑直接使用上面讲的套路，二分出 \(mid\) 之后，对于每个物品将 \(v_i-mid\times c_i\) 作为新的属性，并按其降序排序，贪心取出前 \(m\) 大和 \(0\) 比较即可。

注意这里是最大化，因此是大于等于 \(0\) 符合条件。

时间复杂度：\(\mathcal{O}(n\log^2 v)\)，其中 \(v\) 是答案值域。

代码是很久之前写的了，所以非常丑，那时还没有火车头，码风跟现在相比完全看不出来是同一个人写的：

int n,m,v[205],c[205];
double t[205],ans,l,r;

bool cmp(double a,double b)
{
    return a>b;
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>v[i];
	for(int i=1;i<=n;i++)
		cin>>c[i],r+=v[i];
	while(r-l>1e-6)
	{
		double mid=(l+r)/2.0,ans=0;
		for(int i=1;i<=n;i++) t[i]=v[i]-c[i]*mid;
		sort(t+1,t+n+1,cmp);
		for(int i=1;i<=m;i++) ans+=t[i];
		if(ans>=0) l=mid;
		else r=mid;
	}
	cout<<fixed<<setprecision(3)<<l;
}

洛谷 P4377 [USACO18OPEN] Talent Show G

题目链接

简要题意：有 \(n\) 头奶牛，每头奶牛有两个属性 \(w\) 和 \(t\)，从中选出若干头出来，使得在满足 \(\sum w \ge m\) 的前提下让 \(\frac{\sum t}{\sum w}\) 最大。

同样还是先根据套路，二分 \(mid\)，最终答案大于等于 \(mid\) 的条件为 \(\sum(t-mid\times w) \ge 0\)。

考虑如何解决 \(\sum w\) 的限制，我们可以在二分后将每一个 \(w_i\) 视作物品的重量，\(t_i-mid\times w_i\) 视作物品的价值，然后发现这就变成了一个背包问题（当体积和超过 \(m\) 时，全都算在 \(m\) 的头上），\(\mathcal{O}(nm)\) 的复杂度即可解决。

时间复杂度 \(\mathcal{O}(nm\log v)\)，其中 \(v\) 是答案值域。

int n,m,w[N],t[N];
db f[N],v[N];

bool check(db mid){
	For(i,1,n) v[i]=(db)t[i]-mid*w[i];
	For(i,1,m) f[i]=-inf;
	f[0]=0;
	For(i,1,n) Rof(j,m,0){
		if(j+w[i]>=m) f[m]=max(f[m],f[j]+v[i]);
		else f[j+w[i]]=max(f[j+w[i]],f[j]+v[i]);
	}
	return f[m]>=0;
}

void Main(){
	read(n,m);
	For(i,1,n) read(w[i],t[i]);
	db l=0,r=1e6;
	while(r-l>1e-6){
		db mid=(l+r)/2.0;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%d",int(l*1000));
}

洛谷 P4322 [JSOI2016]最佳团体

题目链接

题意：有 \(n\) 个物品，物品之间的依赖关系为一棵有根树，每个物品有两个属性 \(P\) 和 \(S\)，从中选出若干个使得 \(\frac{\sum P}{\sum S}\) 最大。

二分 \(mid\) 后转化为 \(\sum(P-mid\times S) \ge 0\)。考虑对于树上每个点直接将 \(P_i-mid\times S_i\) 作为其点权，然后设 \(f[u][i]\) 表示以 \(u\) 为根的子树内选了 \(i\) 个点的最大权值，直接跑遍树上背包就行了。

这里的树上背包要求通过不断合并子树进行更新，枚举量时刻不超过当前已并入的子树大小之和，可以证明这样时间复杂度为 \(\mathcal{O}(n^2)\)，虽然我不会证明。

时间复杂度：\(\mathcal{O}(n^2\log v)\)，其中 \(v\) 是答案值域。

struct Edge{
	int nxt,to;
}e[N];

int n,k,cnt,head[N],s[N],p[N],fa[N];
int w[N],v[N],siz[N],f[N][N];

void add_edge(int u,int v){
	e[++cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}

void dfs(int now){
	f[now][1]=v[now];siz[now]=1;
	for(int i=head[now];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==fa[now]) continue;
		dfs(to);siz[now]+=siz[to];
		Rof(j,siz[now],1) For(k,0,min(j-1,siz[to]))
			f[now][j]=max(f[now][j],f[now][j-k]+f[to][k]);
	}
}

bool check(db x){
	For(i,0,n) v[i]=(db)p[i]-x*s[i];
	memset(f,-0x3f,sizeof(f));
	dfs(0);return f[0][k+1]>=0;
}

void Main(){
	read(k,n);
	For(i,1,n){
		read(s[i],p[i],fa[i]);
		add_edge(fa[i],i);
	}fa[0]=-1;
	db l=0.0,r=114514.0;
	while(r-l>1e-6){
		db mid=(l+r)/2.0;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.3lf",l);
}

POJ 2728 Desert King

题目链接

题意：给你 \(n\) 个平面上的点，每个点都有一个高度，两个点之间连边代价是这两点的高度之差（记为 \(c\)），边的长度就是欧几里得距离（记为 \(l\)），试求一棵生成树 \(T\)，要求最小化：

二分 \(mid\)，答案小于等于 \(mid\) 的条件为 \(\sum_{e\in T}(c_e-mid\times l_e) \ge 0\)，考虑直接以此作为新边权求最小生成树，然后将求得的边权和与 \(0\) 比较即可。

考虑是完全图，因此使用 Prim 算法求最小生成树。

时间复杂度：\(\mathcal{O}(n^2\log v)\)，其中 \(v\) 是答案值域。

代码因为特别的原因，不放了。

洛谷 P3199 [HNOI2009]最小圈

题目链接

题意：给你一张 \(n\) 个点 \(m\) 条边的有向图，对于图中任意一个环 \(c\)，定义 \(\mu(c)\) 为该环上所有边的边权的平均值，试求最小的 \(\mu(c)\)。

考虑对于途中的每一个点定义一个点权 \(a_i\)，并令所有的 \(a_i\) 都等于 \(1\)。显然一个环上的点数等于边数，所以此时对于任意一个环 \(c\)，总是有：

二分答案 \(mid\) 之后，显然答案小于等于 \(mid\) 的条件为存在一个环 \(c'\)，使得 \(\mu(c') \le mid\)，即：

由于所有的 \(a_i\) 都是 \(1\)，且 \(|e|=|v|\)，因此可以进一步化简得到：

对于任意的 \(e\in E\)，将 \(w_e-mid\) 作为新边权，然后用 SPFA 找一下此时是否存在负环即可。

时间复杂度：\(\mathcal{O}(nm\log v)\)，其中 \(v\) 是答案值域。

struct Edge{
	int nxt,to;
	db val;
	Edge(int nxt=0,int to=0,db val=0):nxt(nxt),to(to),val(val){}
}e[N];

int n,m,cnt,head[N];
db dis[N];
bool vis[N];

void add_edge(int u,int v,db w){
	e[++cnt]=Edge(head[u],v,w);
	head[u]=cnt;
}

bool spfa(int now,db mid){
	vis[now]=1;
	for(int i=head[now];i;i=e[i].nxt){
		int to=e[i].to;
		if(dis[to]>dis[now]+e[i].val-mid){
			dis[to]=dis[now]+e[i].val-mid;
			if(vis[to]||spfa(to,mid)) return 1;
		}
	}
	vis[now]=0;
	return 0;
}

bool check(db mid){
	For(i,1,n) vis[i]=dis[i]=0;
	For(i,1,n) if(spfa(i,mid))
		return 1;
	return 0;
}

void Main(){
	read(n,m);
	For(i,1,m){
		int u,v;db w;
		scanf("%d%d%lf",&u,&v,&w);
		add_edge(u,v,w);
	}
	db l=-1e7,r=1e7;
	while(r-l>eps){
		db mid=(l+r)/2.0;
		if(check(mid)) r=mid;
		else l=mid;
	}
	printf("%.8lf",r);
}

洛谷 P3705 [SDOI2017]新生舞会

题目链接

二分后直接转化为带权二分图匹配，费用流即可。

本栏目推荐文章
• 2024/1/13 算法笔记
• Python学习笔记
• HDP 笔记
• 学习进度笔记2
• 微软企业库Unity学习笔记(一)
• 微软企业库Unity学习笔记(二)
• kepware关于U-CON的使用笔记 (串口_非主动问答式)
• Anaconda使用笔记
• SHARPNESS-AWARE MINIMIZATION FOR EFFICIENTLY IMPROVING GENERALIZATION论文阅读笔记
• 【做题笔记】数论做题笔记

分数 笔记分数 笔记 分数 笔记16 基本技巧 分数 技巧 笔记 分数 带分数 分数线 百分数 最简分数 真分数 分数178