还记得那场模拟赛，最后一道题我怎么也过不去。题面很短：有若干个物品，每个有收益 $v_i$ 和成本 $c_i$，选一个合法集合 $S$，要求最大化 $\frac{\sum_{i\in S} v_i}{\sum_{i\in S} c_i}$。我当时第一反应是贪心按 $\frac{v_i}{c_i}$ 从大到小取，结果样例都没过。后来才知道，这类目标函数里同时出现分子和分母、而两者都依赖于同一个 0/1 决策的问题，有一个相当系统的名字——01分数规划。
这个名字听起来有点劝退，但它本质上是参数二分 + 判定问题的组合：把原来"除出来的商"最值问题，转成"给定一个阈值，判断存不存在一组选择让商超过这个阈值"。近几年它频繁出现在各类算法竞赛、组合优化课程和一些工程实现里，尤其适合处理平均值、比率、单价这类"每个方案有一个整体比值"的目标。这篇东西不打算写成教科书，我想从自己踩过的坑出发，把整个套路、常见模型、代码细节和实战中的精度陷阱一次讲清楚。老手可以直接跳到后面的"坑点"，新手建议从头读。
1. 从一个"比值最大化"问题开始：为什么直接贪心会翻车
1.1 特例：选 k 个物品使平均值最大时，排序为什么成立
先看最简单的情形：从 $n$ 个物品里恰好选 $k$ 个，每件物品有价值 $v_i$，最大化它们的算术平均值
$$ \max_{|S|=k} \frac{\sum_{i\in S} v_i}{k} $$
这里分母是常数 $k$，所以问题退化成"最大化总和"，按 $v_i$ 从大到小排序，取前 $k$ 个就完了。很多"性价比题"让人产生贪心错觉，根源就是分母固定。但一旦分母从常数变成依赖选择的量，比如"选出的总成本不能超过 $W$，最大化券收益与总成本的比值"，或者干脆"最大化总收益与总成本的比值，没有额外约束"，问题性质就完全变了。
为什么会变？因为 $\frac{\sum v_i x_i}{\sum c_i x_i}$ 不是可加的目标，它没法拆成"每件物品贡献多少"然后独立决策。你按单件比值 $\frac{v_i}{c_i}$ 贪心，忽略了分母共同作用：一个高收益高成本的选项会同时抬高分子和分母，它对整体比值的边际影响不是固定的，而是取决于当前已选集合的分母基数。
1.2 分母跟着决策跑，线性目标就失效了
我举个例子。假设有三个物品：
- 物品 A：收益 10，成本 10，单件比值 1.0
- 物品 B：收益 5，成本 1，单件比值 5.0
- 物品 C：收益 6，成本 100，单件比值 0.06
如果目标是最大化 $\frac{\text{总收益}}{\text{总成本}}$，只选一项，明显选 B，比值 5.0。但如果允许选多项，情况就变得微妙。选 B + A，总收益 15，总成本 11，比值约为 1.36，反而不如只选 B。这说明加入 A 这个"自身比值不差"的物品，会让整体比值下降。这个例子虽然刻意，但足够说明：局部比值高的选项不一定让整体比值高，因为新加入的物品会稀释或改变分母结构。
再看一个相反的例子：某些单件比值不高，但加入后能把整体比值拉高的也大有人在。分子分母都是线性求和，相除之后是非线性函数，而且是离散的选择集合，没有梯度可以依赖。这个领域之所以叫"01 分数规划"，一是决策变量 $x_i\in{0,1}$，二是目标函数是分式形态。0/1 意味着不能取一部分，也意味着问题很多时候是 NP 难的，具体难度取决于限定在什么约束下。
1.3 这类问题的共性特征
碰到下面几个特征，你就要考虑用 01 分数规划的思路了：
- 目标可以写成 $\frac{A(x)}{B(x)}$，其中 $A(x)$ 和 $B(x)$ 都是关于决策变量 $x$ 的线性函数，且分母 $B(x)>0$；
- 决策变量 $x_i$ 只能是 0 或 1，或者某些离散集合（生成树、环、匹配等）；
- 约束条件与具体组合结构绑定，比如"必须形成一棵树""必须是一个环""总重量不超过容量"。
如果你在竞赛里看到"平均收益""最大比值""最小单价""性价比最高"这类词，大概率就是在考这个套路。我在某次组队训练中还见过它伪装成"走一条环，最大化收益时间比"的图论题，题面完全没说分数规划，但剥开就是。
2. 把除法变成减法：目标函数的数学变换与判定性原理
2.1 关键变换：引入参数 $\lambda$
设可行域为 $\mathcal{F}$（所有合法选择的集合），原问题是
$$ r^* = \max_{x\in\mathcal{F}} \frac{A(x)}{B(x)} $$
其中 $A(x)=\sum a_i x_i$，$B(x)=\sum b_i x_i$，并且对任意 $x\in\mathcal{F}$ 都有 $B(x)>0$。
现在我不直接求 $r^*$，而是定义一个辅助问题：对给定的实数 $\lambda$，计算
$$ g(\lambda)=\max_{x\in\mathcal{F}}\big(A(x)-\lambda B(x)\big) $$
这个 $g(\lambda)$ 有一个非常好的性质：单调不增。因为 $\lambda$ 越大，$A(x)-\lambda B(x)$ 对每个 $x$ 来说都越小，取最大值自然也越小。更重要的是，$g(\lambda)$ 的符号与 $r^*$ 和 $\lambda$ 的大小关系直接挂钩。
2.2 符号判定：为什么 $g(\lambda)\ge 0$ 等价于 $\lambda\le r^*$
我们来严格推一遍。任取一个可行方案 $x$，如果它满足
$$ A(x)-\lambda B(x)>0 $$
由于 $B(x)>0$，两边同除以 $B(x)$ 得到
$$ \frac{A(x)}{B(x)}>\lambda $$
也就是说，存在一个可行方案，其比值严格大于 $\lambda$，当且仅当 $g(\lambda)>0$。如果只能等于呢？那就是存在方案使 $A(x)-\lambda B(x)=0$，此时比值恰好等于 $\lambda$。因为可行集是有限集，最大值总能取到，所以更精确的结论是：
- $\lambda < r^*$ 时，存在方案比值大于 $\lambda$，所以 $g(\lambda)>0$；
- $\lambda = r^$ 时，最优方案让 $A(x)-r^B(x)=0$，但可能存在其他方案大于 0 吗？不可能，因为那就意味着有方案比值大于 $r^$，与 $r^$ 是最大值矛盾。所以此时 $g(r^*)=0$；
- $\lambda > r^*$ 时，所有方案比值都小于 $\lambda$，所以每个方案的 $A(x)-\lambda B(x)<0$，最大值仍小于 0，即 $g(\lambda)<0$。
实际写代码时，浮点误差让我们没法严格区分大于 0 和等于 0，所以通常把条件写成 $g(\lambda)\ge 0$。这个判据就成了整个算法的核心。
2.3 直观理解：比值是斜率，减法是判定
有一个非常直观的几何视角。把每个可行方案 $x$ 看作平面上的点 $(B(x),A(x))$，方案与原点连线的斜率就是它的比值。$r^*$ 就是所有点里斜率最大的那个。
给一个 $\lambda$，我们做的事情等价于画一条斜率为 $\lambda$ 且经过原点的直线，然后看有没有可行点在这条直线上方（$A-\lambda B>0$）。有上方点，说明 $\lambda$ 小于最大斜率；所有点都在直线下方，说明 $\lambda$ 大于最大斜率；有点恰好在线上，说明 $\lambda$ 等于最大斜率。这样一来，"求最大斜率"被拆成了"不断猜 $\lambda$，检查是否有点在直线上方"。猜 $\lambda$ 的过程就是二分。
这一步"把除法变减法"是 01 分数规划最灵魂的地方：除法不可加，但减法可加。固定 $\lambda$ 之后，每个元素/边/转移的权值 $a_i-\lambda b_i$ 变成常数，原来那套求最大值、最大值生成树、最长路径、背包 DP 的算法全都能复用。这比直接处理分式友好太多。
3. 二分法的落地与Dinkelbach算法：从理论判据到可运行代码
3.1 通用二分框架
有了 $g(\lambda)$ 的判据，算法外壳其实非常短：
bool check(double lambda) { // 根据子问题计算 g(lambda) = max(A(x) - lambda * B(x)) // 返回 g(lambda) >= 0 } int main() { double l = 0.0; // 下限，需要根据题目调整 double r = 1e9; // 上限，需要根据题目调整 for (int it = 0; it < 80; ++it) { double mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } printf("%.6lf\n", l); return 0; }这里有几个要点：
第一，二分的上下界必须覆盖最优值。如果题目保证收益和成本都是正数，下界取 0 通常没问题；但若允许负数，你可能需要根据所有数据的单件比值算出 $\min$ 和 $\max$，把 $\max$ 当作上界、$\min$ 当作下界。千万别随手r = 1e9就完事，数据范围是 $10^9$ 但比值可能只有 $10^{-6}$，上限对判定结果没影响（只是多一点二分次数），但下限设错会让答案变负。
第二，推荐固定迭代次数，而不是while (r - l > eps)。我见过很多人用while (r - l > 1e-8)，结果在某些边界数据上死循环或者多跑几十次。原因在于浮点数精度有限，当 $l$ 和 $r$ 已经非常接近时，mid可能不再严格位于两者之间，r - l永远停在某个值附近。固定 60~80 次迭代，能稳定把区间缩到 $10^{-18}$ 以下（假设初值区间 $10^9$），完全足够输出误差 $10^{-6}$ 的答案。
第三，$\lambda$ 更新方向别记反。check(mid)返回真说明存在方案比值不小于mid，也就是 $\lambda\le r^*$，所以应该把下界拉高：l = mid。返回假说明所有方案比值都小于mid，r = mid。这个方向错一次，二分出来的就是最小值而不是最大值。
3.2 判定子问题不是"近似"，而是精确最值
很多人写 check 时，只是想"随便找一个方案的 $A-\lambda B$ 非负"。但理论上 $g(\lambda)$ 必须取最大值，因为符号判定依赖最大值。实际判断"是否存在非负方案"可以吗？在可行域有限的情况下，"最大值非负"和"存在一个方案非负"是等价的。所以很多判定算法（比如判正环、求最大生成树）本质就是在找最大值方案，然后看这个最大值是否非负。
这里还藏着一个常见错误：子问题的可行域必须与原问题完全一致。比如原问题要求"选恰好 $n-1$ 条边形成生成树"，你在判定时如果允许随便选若干条边来最大化权值和，那就毁了。因为一个负权边可以不选，但生成树必须凑够边数。后面我专门会讲这个坑。
3.3 Dinkelbach 算法：另一种迭代方式
二分不是唯一的解法。还有一条经典路线叫Dinkelbach 迭代，思路是：
- 随便取初始 $\lambda_0$；
- 在给定 $\lambda_k$ 下求出最优方案 $x_k$，也就是让 $A(x)-\lambda_k B(x)$ 取最大值的那个 $x$；
- 更新 $\lambda_{k+1}=\frac{A(x_k)}{B(x_k)}$；
- 重复直到 $\lambda$ 不再变化。
它的收敛速度通常比二分快（类似于牛顿法），每次得到的 $\lambda_{k+1}$ 单调不降且越来越接近 $r^*$。但实现上要求每次都能拿到"最优方案本身"而不是仅仅最优值，而且有些子问题（比如求最大生成树）可以顺便回溯出方案，有些则比较麻烦。在实际竞赛里，二分已经够用，Dinkelbach 的排序预处理优化在特定场景（如最优比率生成树）里可以大幅减少迭代次数，但代码复杂度也上去了。我的建议是先把二分玩熟，再考虑用它。
4. 两个高频模型：最优比率生成树与最优比率环
4.1 最优比率生成树：判定的关键是"最大生成树"
先看一个经典模型。无向连通图每条边 $e$ 有两个权值 $w_e$（收益）和 $c_e$（成本），选一棵生成树 $T$，最大化
$$ \frac{\sum_{e\in T} w_e}{\sum_{e\in T} c_e} $$
固定 $\lambda$ 后，每条边的新权值设为 $w_e-\lambda c_e$。我们要判定"是否存在生成树，其新权值之和 $\ge 0$"。
注意：这里应该求最大生成树，不是最小。因为"存在一棵生成树权值和非负"等价于"所有生成树中权值和最大的那棵非负"。你把选定的最大值拿来符号判断就行。我最初做这题时惯性用了最小生成树，结果二分全部跑偏——因为我默认"最小化成本"了，但目标是最大化收益率，直线方向反了。
实现上用 Kruskal 或 Prim 都可以。Kruskal 需要对边按新权值排序，而新权值随 $\lambda$ 变化，所以每一轮 check 都要重新排序，复杂度 $O(m\log m)$；80 次二分就是 $80m\log m$。如果图稠密，Prim 的 $O(n^2)$ 有时反而更好。选哪种取决于数据规模。
还有一个非常重要的细节：生成树的边数必须是 $n-1$。Kruskal 即使所有边权都是负数，也必须取 $n-1$ 条，结果是尽量取"负得少"的边。很多人在 check 里贪心地只选正权边，这是错的。负权边会把总和拉低，但你没有不选的权利，因为要形成树。
4.2 最优比率环：正环判定与 SPFA 的细节
另一个高频模型是：有向图每条边有权值 $w_e$ 和 $t_e$，找一个简单环 $C$，最大化
$$ \frac{\sum_{e\in C} w_e}{\sum_{e\in C} t_e} $$
固定 $\lambda$ 后，边权赋为 $w_e-\lambda t_e$。要判断是否存在一个环，其边权和大于等于 0，也就是判断图中是否存在正环。
如果不存在正环，说明所有环的加权和都小于 0，$g(\lambda)<0$，应该把上界往下调；如果存在正环，$g(\lambda)\ge 0$，下界往上调。正环判定我用 SPFA 比较多，每次从所有节点入队，初始距离都设为 0，然后跑最长路。某个节点入队次数超过 $n$，就说明存在正环。为什么初始所有节点入队？因为环可能不出现在从某个固定源点可达的区域内。把所有点同时作为起点，能保证整个图里任意环都被发现。
这里有个实用小技巧：SPFA 判正环时，用普通队列可能会非常慢，尤其在二分次数多的情况下。可以加一个小优化：如果当前节点的"松弛次数"超过 $n$ 就立刻返回真；同时用一个栈而不是队列（也就是 DFS 版 SPFA）在某些随机图上会更快，但可能被刻意构造的数据卡爆。我的经验是：竞赛环境下先用队列版保证正确性，如果超时再考虑 SLF 优化或换 Bellman-Ford。Bellman-Ford 判环虽然 $O(nm)$ 看起来慢，但常数小、不会出现 SPFA 的复杂情况，在 $n$ 关系不大的稀疏图里也是一种稳妥选择。
另外一个容易踩的点：如果你用"最长路"，注意dist[v] < dist[u] + w的初始化。判正环时把所有点距离设为 0 入队，能找到权值为正的环；如果图里存在环权值为 0，正环判定为假，但其实最优比率恰好等于 $\lambda$，用 $\ge0$ 判据会希望为真。浮点精度下通常是 0 附近的小正小负，二分目标不影响最终输出，所以不用过度纠结。
4.3 背包约束下的分数规划：判定变成 DP
除了树和环，这类模型还能嵌进 0/1 背包。比如每个物品有收益 $v_i$、成本 $w_i$，背包容量 $C$，选物品使总成本不超过 $C$，最大化平均收益 $\frac{\sum v_i x_i}{\sum w_i x_i}$。
固定 $\lambda$，每个物品的价值变成 $v_i-\lambda w_i$，问题变成：在总成本不超过 $C$ 的约束下，最大化 $\sum (v_i-\lambda w_i)x_i$。这就是一个普通的 0/1 背包 DP。如果 DP 出来的最大值非负，说明存在方案达到目标比值。复杂度是 $O(nC)$，再乘上二分次数。
这个模型提醒我们：01 分数规划的判定子问题可以是任何已有算法能高效求解的问题。你只需要抓住转换后目标仍然是"线性和最值"这一点，剩下的交给原来的算法。下表总结一下几个常见的映射关系：
| 原问题结构 | 转化后的判定问题 | 常用判定算法 |
|---|---|---|
| 选 $k$ 个物品最大化平均收益 | 将 $v_i-\lambda$ 排序取前 $k$ 大 | 排序 |
| 选生成树最大化收益/成本 | 求最大生成树 | Kruskal / Prim |
| 找环最大化收益/时间 | 判正环 | SPFA / Bellman-Ford |
| 背包容量限制下的平均收益 | 0/1 背包 DP | 动态规划 |
| 选匹配最大化收益/成本 | 最大权匹配 | 匈牙利 / 费用流 |
5. 实战中的几个容易翻车点：精度、负权、迭代次数与判定合法性
5.1 精度控制：别让 EPS 变成玄学
精度问题是 01 分数规划里最容易改到心态爆炸的地方。二分次数和 EPS 怎么选？我现在的习惯是固定 70~80 次迭代，完全不用while (r-l>eps)。这样最终区间宽度足够小，输出时保留题目要求的位数即可。如果你非要用 EPS 作终止条件，建议只用于输出格式控制，比如：
printf("%.6f\n", l + 1e-9);这里加一个极小的 $10^{-9}$ 是为了避免像 0.999999 这类值被四舍五入成错误结果。不过说实话，这种处理依赖具体输出位数，不如直接固定迭代次数踏实。
还有一个细节：check 内部如果涉及大量浮点运算，比如 $a_i-\lambda b_i$，当 $a_i,b_i$ 都是 $10^9$ 量级、$\lambda$ 也是 $10^9$ 时，减法可能产生严重的精度损失。一个补救手段是把所有涉及比较的值转换成 double 后统一排序，尽量少做相等判断。比如判正环时，dist[v] == dist[u] + w这种写法坚决不能出现，要写dist[v] < dist[u] + w - 1e-12。精度上宁可利用"严格小于"判负，也别用带误差的等于判断。
5.2 上下界初始化和负数场景
如果收益或成本可能出现负数，问题会变成另一个话题。一般竞赛题里为了保证 $B(x)>0$，会让成本严格为正，或者限制分母是恒正的量。我强烈建议在写二分前先想清楚：分母是否对任意可行方案都大于 0？如果答案是"否"，那这个问题的数学定义可能本身就不良，因为比值符号会随分母变化。现实中我遇到过的题目几乎都满足分母恒正，所以这条一般不会出幺蛾子。
上下界我通常这样设定：先扫描所有单件/单边，算出
$$ low = \min_{a_i>0} \frac{a_i}{b_i},\quad high = \max_{a_i>0} \frac{a_i}{b_i} $$
但注意这只是初始估计，真正的最优值可能高于所有单件比值（因为组合会改变加权平均的结构）。所以更稳妥的写法是直接给一个足够大的上界，比如所有 $a_i,b_i$ 绝对值的上限相除再乘上一个安全系数。下界同理，如果题目保证答案非负，设 0 没问题。
5.3 判定子问题的"合法选择"陷阱
前面提到了生成树必须选 $n-1$ 条边。我再展开讲两个实际案例。
有次一个同学问我，他的最优比率生成树代码在某个数据上二分死活不收敛。我一看代码，他在 Kruskal 里用if (cnt == n-1) break;没问题，但 check 函数里他写的是：
double sum = 0; sort(edges, edges + m, cmp); for (int i = 0; i < m; ++i) { if (union ok && newW[i] > 0) { sum += newW[i]; } } return sum >= 0;他把"只选正权边"和"生成树必须连通且恰好 n-1 条边"弄混了。正权边优先选没错，但即使全是负权边，你也得把树拼出来，sum 会是负的但不代表没有合法方案。修正方法是老老实实做 Kruskal，选满 n-1 条边再返回总和，哪怕最后总和是负的也要返回，让二分自己去判断符号。
另一个例子是背包分数规划。如果原问题要求总成本恰好等于$C$，那 DP 初始化时只能把 $dp[0]=0$，其他位置设为无穷小。如果你偷懒把其他位置也设成 0，相当于允许成本不足 $C$ 的方案参与比大小，最后 check 可能偏向错误方向。这类"可行域变形"问题非常隐蔽，我自己的经验是：每次写 check 前，先在心里把原问题可行域重新描述一遍，再问自己判定算法是否严格在这个域上取最值。
5.4 判定子问题的性能取舍
二分次数一旦上到 80 次，子问题的复杂度就被放大了 80 倍。所以子问题选型不能只看单次复杂度，还要看常数和实现难度。
- 最优比率生成树：边数 $m$ 很大时，每次 Kruskal 排序 $O(m\log m)$ 可能跑不过稠密图上的 Prim $O(n^2)$。但如果 $m$ 接近 $n^2$，Prim 的平方复杂度反而稳。
- 最优比率环：SPFA 判正环在大多数随机图上很快，但遇到 $n=10^5$ 级别的图，可能要换思路。有些题可以利用图的结构（比如每个点入度很小）直接枚举环。
- 如果子问题本身是背包 DP，$nC$ 再乘二分次数很容易超时。这时可以考虑把二分次数降到 50，或者用 Dinkelbach 算法减少迭代轮数。Dinkelbach 在背包分数规划场景下经常只需要几十次以内迭代，比二分快不少。
我个人的常用策略是：先写最不容易出错的版本（Kruskal + SPFA + 固定 70 次），通过样例后看数据规模，如果卡常数再逐个优化。切忌一开始就上 SLF 优化、手写堆、压位 DP 这些花活，代码复杂了 bug 也跟着变多。
5.5 从"会不会用"到"什么时候想到用"
最后再说一点从解题者角度的心得。很多时候难点不是实现，而是根本想不到这题能用 01 分数规划。我的判断套路是：
- 看目标函数是不是"一个和除以另一个和"；
- 看分子分母是否都被同样的 0/1 变量控制；
- 看除了这个分式目标以外，是否还有一组常规约束（树、路径、环、背包、匹配、区间选点）。
只要三个条件都满足，十有八九就是二分 $\lambda$ + 原约束下的线性最值判定。你再想想有没有一个已知算法能在固定权值下求最优方案，如果有，这题就只剩写代码了。
我见过不少人把这类题归为"套路题"，但我不完全认同。套路只是外壳，真正难的是在不同约束之间切换判定算法，以及处理二分过程中的各种边界情况。把这套思路内化成一种条件反射后，再遇到"最大化平均值""最小化费率"这类表达，你第一反应就不会是贪心，而是先画一条斜率为 $\lambda$ 的直线，然后问自己：给定这条直线，我能不能高效找出有没有点在它上方？这一问，很多问题就豁然开朗了。
