分数规划
分数规划用来求一个分式的极值．其形式化表述是，给出 𝑎𝑖ai
和 𝑏𝑖bi，求一组 𝑤𝑖 ∈{0,1}wi∈{0,1}，最小化或最大化
𝑛∑𝑖=1𝑎𝑖×𝑤𝑖𝑛∑𝑖=1𝑏𝑖×𝑤𝑖∑i=1nai×wi∑i=1nbi×wi
通俗来讲，这类问题类似于：每种物品有两个权值 𝑎a 和 𝑏b，选出若干个物品使得 ∑𝑎∑𝑏∑a∑b 最小或最大．
一般分数规划问题还会有一些特殊的限制，比如「分母至少为 𝑊W」．
求解
二分法
分数规划问题的通用方法是二分答案法．假设当前二分到的答案为 𝑚𝑖𝑑mid，则一组满足条件的 {𝑤𝑖}{wi} 会让权值大于等于 𝑚𝑖𝑑mid．根据这一条件列不等式并变形
∑𝑎𝑖×𝑤𝑖∑𝑏𝑖×𝑤𝑖≥𝑚𝑖𝑑⟹∑𝑎𝑖×𝑤𝑖−𝑚𝑖𝑑×∑𝑏𝑖⋅𝑤𝑖≥0⟹∑𝑤𝑖×(𝑎𝑖−𝑚𝑖𝑑×𝑏𝑖)≥0∑ai×wi∑bi×wi≥mid⟹∑ai×wi−mid×∑bi⋅wi≥0⟹∑wi×(ai−mid×bi)≥0
那么只要求出不等号左边的式子的最大值就行了．如果最大值比 00 要大，说明 𝑚𝑖𝑑mid 是可行的，否则不可行．分数规划的主要难点就在于如何求 ∑𝑤𝑖 ×(𝑎𝑖 −𝑚𝑖𝑑 ×𝑏𝑖)∑wi×(ai−mid×bi) 的最大值或最小值．
Dinkelbach 算法
Dinkelbach 算法1的大概思想是每次用上一轮的答案当做新的 𝐿L 来输入，不断地迭代，直至答案收敛．
例题
有 𝑛n 个物品，每个物品有两个权值 𝑎a 和 𝑏b．求一组 𝑤𝑖 ∈{0,1}wi∈{0,1}，满足 𝑤𝑖wi 中恰好有 𝑘k 个 11，最大化 ∑𝑎𝑖×𝑤𝑖∑𝑏𝑖×𝑤𝑖∑ai×wi∑bi×wi 的值．
解法
把 𝑎𝑖 −𝑚𝑖𝑑 ×𝑏𝑖ai−mid×bi 作为第 𝑖i 个物品的权值，贪心地选权值前 𝑘k 大的物品．若权值和大于 00 则可行，否则不可行．
参考代码
---|---
[洛谷 4377 Talent Show G](https://www.luogu.com.cn/problem/P4377)
有 𝑛n 个物品，每个物品有两个权值 𝑎a 和 𝑏b．
你需要确定一组 𝑤𝑖 ∈{0,1}wi∈{0,1}，使得 ∑𝑤𝑖×𝑎𝑖∑𝑤𝑖×𝑏𝑖∑wi×ai∑wi×bi 最大．
要求 ∑𝑤𝑖 ×𝑏𝑖 ≥𝑊∑wi×bi≥W．
解法
本题多了分母至少为 𝑊W 的限制，因此无法再使用上一题的贪心算法．
可以考虑 01 背包．把 𝑏𝑖bi 作为第 𝑖i 个物品的重量，𝑎𝑖 −𝑚𝑖𝑑 ×𝑏𝑖ai−mid×bi 作为第 𝑖i 个物品的价值，然后问题就转化为背包了．那么 𝑑𝑝[𝑛][𝑊]dp[n][W] 就是最大值．
在 DP 过程中，物品重量和可能超过 𝑊W，此时直接视为 𝑊W 即可．
参考代码
---|---
每条边有两个权值 𝑎𝑖ai 和 𝑏𝑖bi，求一棵生成树 𝑇T 使得 ∑𝑒∈𝑇𝑎𝑒∑𝑒∈𝑇𝑏𝑒∑e∈Tae∑e∈Tbe 最小．
解法
把 𝑎𝑖 −𝑚𝑖𝑑 ×𝑏𝑖ai−mid×bi 作为每条边的权值，那么最小生成树就是最小值．本题中需要求解一个完全图中的最小生成树，应利用 Prim 算法求解．
参考代码
---|---
[[HNOI2009] 最小圈](https://www.luogu.com.cn/problem/P3199)
每条边的边权为 𝑤w，求一个环 𝐶C 使得 ∑𝑒∈𝐶𝑤|𝐶|∑e∈Cw|C| 最小．
解法
把 𝑎𝑖 −𝑚𝑖𝑑ai−mid 作为边权，那么权值最小的环就是最小值．
因为我们只需要判最小值是否小于 00，所以只需要判断图中是否存在负环即可．
另外本题存在一种复杂度 𝑂(𝑛𝑚)O(nm) 的算法，如果有兴趣可以阅读 [这篇文章](https://www.cnblogs.com/y-clever/p/7043553.html)．
参考代码
---|---
习题
- JSOI2016 最佳团体
- SDOI2017 新生舞会
- UVa1389 Hard Life
- [洛谷 P2868 [USACO07DEC] Sightseeing Cows G](https://www.luogu.com.cn/problem/P2868)
- AtCoder Beginner Contest 324 F - Beautiful Path
参考资料与注释
- Dinkelbach, Werner. "On nonlinear fractional programming." Management science 13.7 (1967): 492-498. ↩
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：StudyingFather, Ir1d, Tiphereth-A, H-J-Granger, countercurrent-time, greyqz, NachtgeistW, Early0v0, Enter-tainer, Mout-sea, AngelKitty, banglee13, CCXXXI, cjsoft, diauweb, ezoixx130, GekkaSaori, hsfzLZH1, huaruoji, Konano, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, sshwy, Suyun514, weiyong1024, alphagocc, c-forrest, ChungZH, GavinZhengOI, Gesrua, Henry-ZHR, HeRaNO, ksyx, kxccc, lyccrius, lychees, MicDZ, ouuan, Peanut-Tang, r-value, SukkaW, Xeonacid 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用