分数规划

分数规划用来求一个分式的极值。

形象一点就是，给出 和 ，求一组 ，最小化或最大化

另外一种描述：每种物品有两个权值 和 ，选出若干个物品使得 最小/最大。

一般分数规划问题还会有一些奇怪的限制，比如『分母至少为 』。

求解

二分法

分数规划问题的通用方法是二分。

假设我们要求最大值。二分一个答案 ，然后推式子（为了方便少写了上下界）：

那么只要求出不等号左边的式子的最大值就行了。如果最大值比 要大，说明 是可行的，否则不可行。

求最小值的方法和求最大值的方法类似，读者不妨尝试着自己推一下。

Dinkelbach 算法

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

---

分数规划的主要难点就在于如何求 的最大值/最小值。下面通过一系列实例来讲解该式子的最大值/最小值的求法。

实例

模板

有 个物品，每个物品有两个权值 和 。求一组 ，最大化 的值。

把 作为第 个物品的权值，贪心地选所有权值大于 的物品即可得到最大值。

为了方便初学者理解，这里放上完整代码：

---

为了节省篇幅，下面的代码只保留 check 部分。主程序和本题是类似的。

POJ2976 Dropping tests

有 个物品，每个物品有两个权值 和 。

你可以选 个物品 ，使得 最大。

输出答案乘 后四舍五入到整数的值。

把第 个物品的权值设为 ，然后选最大的 个即可得到最大值。

洛谷 4377 Talent Show

有 个物品，每个物品有两个权值 和 。

你需要确定一组 ，使得 最大。

要求 。

本题多了分母至少为 的限制，因此无法再使用上一题的贪心算法。

可以考虑 01 背包。把 作为第 个物品的重量， 作为第 个物品的价值，然后问题就转化为背包了。

那么 就是最大值。

一个要注意的地方： 可能超过 ，此时直接视为 即可。（想一想，为什么？）

POJ2728 Desert King

每条边有两个权值 和 ，求一棵生成树 使得 最小。

把 作为每条边的权值，那么最小生成树就是最小值，

代码就是求最小生成树，我就不放代码了。

[HNOI2009]最小圈

每条边的边权为 ，求一个环 使得 最小。

把 作为边权，那么权值最小的环就是最小值。

因为我们只需要判最小值是否小于 ，所以只需要判断图中是否存在负环即可。

另外本题存在一种复杂度 的算法，如果有兴趣可以阅读 这篇文章。

总结

分数规划问题是一类既套路又灵活的题目，一般使用二分解决。

分数规划问题的主要难点在于推出式子后想办法求出 的最大值/最小值，而这个需要具体情况具体分析。

习题

• JSOI2016 最佳团体
• SDOI2017 新生舞会
• UVa1389 Hard Life