做分数规划这类题目，很多人第一次看到题解里“二分答案 + check”那一套，总觉得像是凭空冒出来的思路。我自己最开始刷“算法提高16.01分数规划”这个专题时也是一脸懵：一个求最优比率的问题，怎么就变成二分判定问题了？后来又遇到一堆变种，什么最优比率生成树、最优比率环，发现万变不离其宗。这篇就按我个人从入门到实战的路径，把这个专题完整拆开聊一遍，把模型、原理、代码和坑都摆出来。
适合看这篇的人，主要是正在刷算法提高专题、遇到分数规划却无从下手的同学，或者是想彻底搞懂“为什么能二分”而不是只背板子的参赛选手。内容不涉及高深数学，只要你有基础的二分思想，会写最短路或者最小生成树，就能跟着走完整个过程。
1. 先把分数规划的问题模型搞清楚
1.1 从一道生活题说起
我们经常遇到这样的问题：有 n 个东西，每个东西都有一个收益 a_i 和一个代价 b_i，现在要在这 n 个东西里选若干个，使得选出来的东西总收益和总代价的比值最大。注意，这里不是简单的总和最大，而是两个总和的比值最大。
举个最直观的例子。你有几门课的成绩，每门课有“学分”和“分数”，现在你可以放弃其中若干门课，目标是让剩余课程的平均分最高。这时候每门课的 b_i 是学分，a_i 是这门课的成绩乘以学分。你放弃几门分低的课，平均分确实会上去，但你得想想：放弃课程会导致分母也变小，所以“贪心地放弃最低分”并不一定最优。这就是分数规划要处理的核心矛盾：分子和分母同时随选择变化，不能拆开看。
再换一个大家熟悉的实际场景：给你若干组数据，每组有完成的工作量和消耗的时间，你要选几组，使得“总工作量 / 总时间”最大。直接一个个比较“单位时间工作量”然后排序选最大的，只有在能拆开按比例取的时候才成立；一旦要求整体选择，这种贪心就会失效。
1.2 从实际需求抽象出数学模型
把所有选择抽象一下，假设我们有一个变量 x_i ，表示“第 i 个元素是否被选中”，取 0 或 1。那么我们要最大化的目标就是：
最大化：Σ(a_i * x_i) / Σ(b_i * x_i)其中 b_i 通常要求为正数。分母不能为 0，所以至少得选一个元素。
这类问题统称分数规划，又叫比率规划。“16.01 分数规划”这个专题编号常见的命名方式，其实指的就是这类问题。核心难点是：目标函数既不是线性的，也不是凸的，直接求导、直接动态规划都不太好办。但它的特殊之处在于，我们关心的不是每一项的比值，而是整体加和之后的比率。
关键转化来了。假设我们猜测最终最优值是 r，也就是说存在一种选择方案，让分子和分母的比值 ≥ r，那么这个条件等价于：
Σ(a_i * x_i) - r * Σ(b_i * x_i) ≥ 0把它改写一下：
Σ((a_i - r * b_i) * x_i) ≥ 0看到没，右边变成了一个关于 x_i 的线性求和式。每一项的“价值”变成了 (a_i - r * b_i)。如果我们要判断是否存在一个选法让这个式子大于等于 0，那就变成了一个非常普通的问题：从一堆物品中，按照某个规则挑选若干物品，使得选中物品的“新价值”之和最大，再看这个最大值是否非负。
这个变换，是整个分数规划专题的灵魂。
1.3 分数规划常见的三种形式
在算法题里，分数规划很少单独出现，通常是作为“外壳”套在别的经典算法外面。我按自己刷题遇到的频率整理一下。
第一种是最基础的 01 分数规划，也就是上面那种“选若干物品最大化比率”。典型解法是二分 r，然后根据新价值是否大于 0 判断。判断的时候往往还要加一个约束，比如“恰好选 k 个”“至少选 k 个”“最多选 k 个”，那就对应不同的子问题，比如排序取前 k 个、背包 DP 等。
第二种是最优比率生成树。题目给你一张图，每条边有两个权值，比如“成本”和“收益”，要你找一棵生成树，让这棵树的“总收益 / 总成本”最大。二分 r 之后，每条边的权值变成 a_i - r * b_i，判断是否存在生成树使得总权值 ≥ 0。这时候套的就是最小生成树算法，只是边权被重新定义了。
第三种是最优比率环。这个稍微绕一点，给一个有向图，每条边有权值 a_i 和 b_i，要找一个环，使得环上所有边的“总收益 / 总代价”最大。二分 r 之后，每条边的权值变成 a_i - r * b_i，要找是否存在一个正环。正环判断一般用 SPFA 的某个变种，这也是很多人觉得难的地方。
无论是哪一种，核心都逃不过那个关键变换：把“比值 ≥ r”变成“线性值 ≥ 0”，然后用已知算法去判定。这也是为什么我建议先把第一种吃透，后面两种就是套壳。
2. 二分法：为什么“猜答案”可行
2.1 二分的是答案，不是选择方案
很多人看到“二分答案”四个字，第一反应是：我们不是要找最优的选择方案吗，怎么变成猜一个数了？这里的关键在于，分数规划最优值的范围通常比较容易确定，而且判断“当前猜的值是否可行”是相对容易的。我们并不需要直接构造出最优方案，而是通过不断收缩答案区间，逼近那个最优比率。
假设我们猜了一个值 r，然后对所有元素计算差值 c_i = a_i - r * b_i。如果存在一个可行选择方案，使得中选元素的 c_i 之和大于等于 0，那么说明最优值至少是 r，也就是答案在 [r, 上界] 区间里；如果无论怎么选，这个和都小于 0，说明我们想要的比率根本达不到 r，答案应该比 r 小。
之所以可以二分，是因为这个判定结果关于 r 是单调的。r 越小，c_i = a_i - r * b_i 越大，显然越容易满足“之和 ≥ 0”；r 越大，c_i 越小，越不容易满足。所以存在一个临界点，低于它答案可行，高于它不可行，这个临界点就是最优比值。
这个单调性非常重要。它不是“看起来像”单调，而是严格单调：因为 b_i 都是正的，r 增大时每一项 c_i 都严格减少（或者至少不增），总和也严格减少，所以一旦某个 r 可行，那么任何比它小的 r 也一定可行。这就保证了二分完全正确。
2.2 判定问题的具体化
现在问题聚焦到了：给定 r 和所有 c_i，如何判断是否存在合法选法让所选元素的 c_i 之和 ≥ 0。
如果是 01 分数规划“选任意多个”，那我们直接看所有 c_i 中正数的和是否 ≥ 0 就行，因为全是正数的都选上肯定最优，负数的都不选。如果要求“恰好选 k 个”，那就是选出 c_i 最大的 k 个，看前 k 大之和是否大于等于 0。
这里要注意：排序选前 k 大之所以能成立，是因为判断条件里没有其他相互依赖的约束。一旦加上“必须选满 n 个中的某部分”“分组一定要达到某条件”，那就可能要用背包 DP 或者网络流来判定。很多分数规划题目的难点其实在这里，分数规划本身只提供了外层框架。
我自己做题的习惯是，先把判定子问题抽象出来，明确要套用什么算法。比如：
- 选 k 个最大值：排序
- 选一个生成树：最小生成树
- 选一个环：SPFA 判正环
- 选若干物品且容量有限：背包 DP
只要判定算法是多项式复杂度，外面的二分次数一般是 50 到 60 次，整体复杂度基本可控。
2.3 check 函数的编写要点
编写二分判定函数时，有一个细节非常重要：c_i 的浮点误差。由于 a_i 和 b_i 可能是很大的整数，r 是浮点数，计算 c_i = a_i - r * b_i 时要注意精度损失。更稳妥的做法是使用更高精度的浮点数，或者在特殊情况下把比较转化为整数运算。
举个例子，假设 a_i 和 b_i 都是整数，我们要判断“前 k 个 c_i 之和是否 ≥ 0”。如果直接用浮点数累加，最终和特别接近 0 时可能因为误差导致判错。这时候可以把不等式左右都乘以一个数，或者干脆在累加时用 long double，等排序完后再和 0 比较。
另一个重点是二分的边界。最优比率不会超过 max(a_i / b_i)，所以二分上界可以取这个最大值，下界取 0。也有人为了省事直接取一个很大的数，比如 1e12，但这样会白白多算几次二分。我建议还是老老实实求一个合理的上界，一方面减少迭代次数，另一方面防止浮点数在极大值附近丢失精度。
二分次数怎么定也很关键。很多人用 while (r - l > eps) 来判断，但这样容易因为 eps 设得不对而无限循环。我推荐直接固定循环 60 次或者 80 次，每次把区间缩小一半。这样不用纠结 eps 该设多少，也能保证精度足够。原因很简单：double 的有效位数有限，固定迭代次数比固定差值更可控。
3. 经典例题实操：考试放弃题
3.1 题目设计与建模过程
为了把上面的思路落下来，我们用一个经典题目走一遍完整流程。假设有 n 门考试，第 i 门考试的总分是 b_i，你得了 a_i 分。现在学校允许你放弃其中 k 门课，问剩余课程的平均分最高可以是多少。
平均分的定义是：剩余课程得分之和 / 剩余课程满分之和。注意，不是把每门课单独算百分制再取平均，而是加权平均，权重就是每门课的满分。这一点很关键，很多人一开始会理解错。
建模过程是这样的：每门课其实是一个物品，b_i 是满分，a_i 是得分。我们要从 n 个物品中去掉 k 个，相当于选择剩余的 n-k 个物品，让 Σa_i / Σb_i 最大。这里“选多少个”是固定的，所以到了二分判定环节，我们会计算所有 c_i = a_i - r * b_i，然后排序，取最大的 n-k 个，看它们的和是否 ≥ 0。
细想一下，为什么要取最大而不是最小？因为我们要判断“是否存在一种选法，让所选物品的 c_i 之和 ≥ 0”，在选固定数量 m 个物品时，肯定选 c_i 最大的 m 个最有利。如果这 m 个最大的加起来都小于 0，那其他任何选法更不可能满足条件。这个逻辑非常直接。
3.2 完整代码实现
我直接用 C++ 写一版完整实现，思路就是二分套排序判定。假设输入 n 和 k，然后两个数组 a 和 b，最后输出最大平均分。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; int n, k; double a[MAXN], b[MAXN]; double c[MAXN]; bool check(double r) { for (int i = 0; i < n; i++) { c[i] = a[i] - r * b[i]; } sort(c, c + n, greater<double>()); double sum = 0; int m = n - k; for (int i = 0; i < m; i++) { sum += c[i]; } return sum >= 0; } int main() { while (scanf("%d%d", &n, &k) == 2) { if (n == 0 && k == 0) break; for (int i = 0; i < n; i++) scanf("%lf", &a[i]); for (int i = 0; i < n; i++) scanf("%lf", &b[i]); double l = 0, r = 0; for (int i = 0; i < n; i++) { r = max(r, a[i] / b[i]); } for (int iter = 0; iter < 60; iter++) { double mid = (l + r) / 2; if (check(mid)) { l = mid; } else { r = mid; } } printf("%.6lf\n", l); } return 0; }这段代码是一个完整可运行的程序，核心就是 check 函数。我故意把 a 和 b 声明为 double，是为了让代码简洁，但如果输入是整数，改成 long long 读入、在 check 内部转成 double 计算会更好，避免大整数在浮点数转换时出现意外误差。
输出的精度也要注意。二分 60 次之后，区间长度大约是初始区间长度除以 2 的 60 次方，早就超过 double 的精度极限了。所以输出 l 或者 r 都可以，但保留 6 位小数是最常见的做法。有些题目要求百分比输出或者保留 3 位小数，那就按照题目要求来。
3.3 复杂度与精度分析
这个解法的时间复杂度分两块。一块是外层二分，固定 60 次。一块是每次 check 里的排序，复杂度 O(n log n)。所以总复杂度是 O(60 * n log n)，n 到 1e5 的时候大概能跑进一两秒，n 到 1e6 就有点悬了。
如果题目 n 特别大，但恰好不需要排序，而是用 nth_element 只取前 m 个，就可以把 check 降成 O(n)。我提供的是排序版本，因为通用性和可读性更好；实际比赛里如果 T 组数据且 n 巨大，我会改成 nth_element 优化。
关于精度，有一个实用性建议：如果 a_i 和 b_i 都是整数，而且题目要求输出百分数（也就是把平均分乘以 100），那么在 check 里可以直接比较：
a[i] * 100 - r * b[i] >= 0这样 r 表示的是“百分制平均分”，避免最后输出的时候还要再乘一次导致二次误差。我见过不少同学二分时用的是原始分数，输出时才乘 100，结果因为浮点误差差了 0.01 被卡。这种细节最冤枉，写代码时提前想清楚单位，能省很多事。
4. Dinkelbach 算法：另一种迭代思路
4.1 用最优解不断逼近最优值
除了二分，分数规划还有一个经典迭代算法叫 Dinkelbach 算法。它的思路更像是在“用上一次的最优方案来修正当前的候选答案”。
具体来说，我们从一个初始猜测值 r 开始。在当前 r 下，找到使得 Σ(a_i - r * b_i) 最大的选择方案，假设这个最大和是 F(r)。如果 F(r) ≥ 0，我们可以把 r 更新为“当前最优选法”的实际比率，即：
r_new = Σa_i / Σb_i （这里的选法是刚才求出的最优选法）然后重复这个过程，直到 r 的变化小到可以忽略。
为什么有效？因为每次更新后的 r_new 一定是比之前更优的下界，而且每次选法对应的实际比率会单调递增。这个算法的收敛速度通常比二分快，尤其在后半段，往往几次迭代就能达到很高精度。
4.2 实际对比：何时选二分，何时选 Dinkelbach
从编码角度讲，二分更直观，不容易写错；Dinkelbach 则需要你额外保存“当前最优方案所选元素”的和，代码量稍微多一点，而且要求判定问题本身能方便地求出最优方案，而不只是判定可行性。
从效率角度讲，Dinkelbach 的迭代次数在多数情况下远小于 60 次，可能十几二十次就收敛了。但它的每轮迭代同样要跑排序或者最短路，所以实际差别不是特别大。不过有一点，Dinkelbach 适合那些 check 过程本身就能返回最优选择方案的场景；如果判定算法只能返回一个 bool，那还是用二分省事。
我个人的习惯是：比赛时默认写二分，因为时间复杂度可控、鲁棒性强；只有在 T 组数据特别多、二分次数明显成为瓶颈时，才改用 Dinkelbach。还有一种情况，就是判定问题本身用的是 SPFA 判正环这类复杂算法，每多一次迭代都心惊胆战，这时候 Dinkelbach 的快速收敛优势就很明显了。
需要注意，Dinkelbach 对初值有一定依赖。如果初值设得太离谱，第一轮迭代可能导致更新出很奇怪的结果。我的做法是取所有 a_i / b_i 的最大值作为初值，反正这个值必然不小于最终答案，迭代起来很快。
5. 分数规划的变种问题拓展
5.1 最优比率生成树的二分判定
前面提到，最优比率生成树也是同一套路。现在假设每条边有两个属性 cost 和 value，要选 n-1 条边形成生成树，让 value 之和与 cost 之和的比值最大。
在二分到 r 时，每条边的新权值是 value_i - r * cost_i。我们需要判断是否存在一棵生成树让总权值 ≥ 0。注意，这里不是求最小生成树随便判断一下，而是要判断“最大可能的生成树权值”是否非负。用最小生成树算法求出来的其实是最小权值，如果最小权值都 ≥ 0，那所有生成树都 ≥ 0；但我们要判断的是是否存在某一棵 ≥ 0，所以应该求最大生成树。
这个问题我踩过坑：用 Kruskal 时习惯性按边权从小到大排序，结果一直错。最优比率生成树应该按新边权从大到小排序，找最大生成树，看总权值是否 ≥ 0。这里的“最大”不是指收益最大，而是指在当前 r 下新权值之和最大，这样才能最大化满足条件的机会。
复杂度方面，二分 60 次，每次 Kruskal 是 O(m log m)，m 是边数。如果边数到 2e5，总复杂度就是 60 * 2e5 * log，通常情况下可以接受，但要注意常数。我试过在一些 OJ 上用 Kruskal 套分数规划，如果不加优化，很容易超时。可以提前把边按原始 cost 排序，减少每次重排的工作；不过新权值依赖 r，严格来说没法完全复用排序结果，只能尽量优化常数。
5.2 最优比率环与正环判定
最优比率环是另一个常见变种，也是我个人觉得最容易绕晕的。
给定有向图，每条边有收益 w_i 和花费 t_i，找一个有向环，让环上总收益 / 总花费最大。二分 r 后，每条边的新权值是 w_i - r * t_i，我们要判断是否存在一个环，使得环上所有边的新权值之和 ≥ 0。换句话说，判断图中是否存在正权环。
正权环的判定有两种常见做法。一种是把权值取反，然后判负环，用 SPFA 的标准写法；另一种是直接用最长路加入队次数判正环。我推荐第一种，因为判负环的 SPFA 模板更常见，不易写错。
具体实现时，注意初始化：判负环要初始化为 INF，判正环要初始化为 0 或 -INF；入队次数超过 n 说明存在环。这里有个细节，如果图本身不连通，要多次从不同起点跑 SPFA，或者建一个超级源点连向所有点，否则会漏判。
最优比率环还有一个坑：二分时 r 的初始上界不能用简单的 max(w_i/t_i) 来算，因为环是整体加和，单条边的比率不能代表整个环的比率。我的做法是设一个较大的上界，比如 1e7，或者根据题目数据范围算一个保底值。反正 SPFA 判定本身不慢，多几次二分问题不大。
5.3 分数规划与背包 DP 的组合
还有一种变种比较少见但很有代表性：选出的物品数量不固定，但受到某个总容量限制。比如每个物品有体积，背包容量是 V，要从物品中选一个子集，让总收益 / 总花费最大。
这种问题在二分到 r 后，判定就变成了一个 0/1 背包问题：每个物品价值是 w_i - r * c_i，要求在体积不超过 V 的前提下，最大化所选物品的价值之和，再看这个最大值是否 ≥ 0。
这里的复杂度就和前面的排序题明显不同了。背包 DP 的复杂度是 O(n * V)，外面再乘 60 次二分，必须注意 V 的大小。如果 V 到 1e5、n 到 100，整体勉强能过；如果 V 到 1e6，那就得考虑优化，比如可行性背包转成完全背包等。但不管怎样，框架还是一样的：二分 r，然后套背包判定。
从这些变种可以看出，分数规划本身并不难，难的是挂在它下面的那层“判定算法”。所以我的建议是：先确保自己对排序、最小生成树、SPFA、背包 DP 这些基础算法非常熟练，再来攻克分数规划专题，会顺畅很多。我最初就是基础算法不牢，结果在判定环节反复出错，还以为是分数规划本身理解错了。
6. 常见问题与避坑技巧实录
6.1 二分边界设错导致答案偏移
我见过很多初学者把二分上界直接设成一个很大的常数，比如 1e9，然后循环 50 次，发现答案偏大或者偏小。原因在于浮点数在非常大和非常小之间二分时，后半段可能已经达到了浮点精度极限，继续二分只是在一个区间内抖动，不会继续收敛。
正确做法是先扫描一遍所有元素，求出 a_i / b_i 的最大值作为 r 的上界。这个值一定不小于最终答案，因为单独选某个物品的比率不可能超过所有物品中的最大比率，整体比率也不会超过它。数学上很好理解，分子的加权平均除以分母的加权平均，不可能大于各个分子分母比值的最大值，这是加权平均的基本性质。
6.2 排序方向搞反
这个错误特别隐蔽。在“去掉 k 个物品”的题目里，我们要选最大的 n-k 个 c_i 值；在“生成树”里，我们要找最大生成树；在“环”里，我们要找正环。看起来都是“最大”，但这和很多人写惯了的“最小生成树”“最短路径”套路不一样，容易习惯性搞反。
我自己有一次写最优比率环，SPFA 判的是负环，结果一直以为代码写错，折腾了半天才发现是判环方向反了。后来我给自己定了一条规则：分数规划的所有判定，先想清楚“我要不要最大化这个新权值的和”，然后顺着目标选算法。最大化用最长路、最大生成树；最小化用最短路、最小生成树，分清之后再动手写代码。
6.3 精度比较时使用 eps 不当
判断 sum >= 0 时，有人喜欢写 sum >= -eps，认为这样更宽容；有人写 sum >= eps，认为这样更严格。这个选择其实取决于你二分后输出的目标是最大值还是最小值，以及你二分循环的条件。
我的建议是：如果使用固定迭代次数二分，check 里直接和 0 比较就行，不需要 eps。因为二分循环结束时，答案的误差已经由迭代次数保证了，check 里的微小偏差不会影响最终输出的位数。如果你非要用 while (r - l > eps)，那 eps 至少要设在 1e-8 以下，并且配合 long double 使用，否则容易死循环或者结果差一位。
6.4 输出格式要求是百分数还是小数
很多分数规划题目要求输出百分数，比如保留三位小数加一个百分号。你在二分时的 r 是原始比率，输出前要乘以 100，这时候可能出现 0.001 的精度问题。
我建议在输入后直接把 a_i 或 b_i 按要求缩放。如果输出百分数且保留三位小数，可以在 check 里把 r 当作百分数来算，这样代码里处理的单位与输出单位一致，减少一次换算误差。这个方法虽然听起来只是小技巧，但真的能救你于卡精度之中。
6.5 大数据读取与常数优化
分数规划结合排序的版本，主要瓶颈在排序上。如果 n 达到 1e6，每次 check 都完整排序会非常吃力。一个常用优化是改用 nth_element 只取第 k 大，并同时求前 k 大之和，这样复杂度从 O(n log n) 降到 O(n)。
还有一个小技巧：对于“选前 m 个最大值之和”，不需要把所有 c_i 都存下来再排，可以在生成 c_i 时同时维护一个大小为 m 的最小堆，堆内元素就是当前最大的 m 个。这样空间复杂度可能更高，但思路一样。具体用哪种，取决于你更在乎代码简洁性还是极限性能。
6.6 多组数据时注意二分重置
这个看起来是基础问题，但真的很常见。多组输入时，上界 r 和数组内容都要重新初始化。我见过一个同学，因为上界没有重置，第一组数据算出一个很大的上界，第二组数据小一点，二分直接从错误范围开始，结果答案完全不对。
我的习惯是：每组数据进来后，除了读入数组，还要把 r 初始化为 0，然后再做扫描求最大值。这个操作虽然不起眼，但能避免一个很恶心的排查过程。
7. 一点个人经验分享
分数规划这个专题，最难的不是那套二分框架，而是你能不能识别出题目背后的比率结构。很多时候题目会把“收益”和“代价”隐藏起来。比如“每位应聘者有工作能力和期望薪资，选若干人让总能力 / 总薪资最大”，本质就是 01 分数规划。多练几道题之后，你会逐渐形成一种直觉：只要看到“比率”“平均”“单位成本收益”这些词，就该往分数规划上想。
如果一定要说一个最重要的技巧，那就是把所有问题都转化到“判断是否存在选法使新权值之和非负”这一层。之后无论面对生成树、环还是背包变种，思路都会特别清晰。做专题训练时，不要急着看题解，先自己想清楚：如果二分一个数，check 函数里该做什么？这个问题的答案往往是解题的核心。
最后说个实践建议：把经典题目换着写法做一遍。同一道 01 分数规划，先用二分写一遍，再用 Dinkelbach 写一遍，然后在相同数据下对比两者的输出和运行时间。这个对比做完，你对该算法的理解绝对比看十篇题解都深刻。
