01分数规划：二分答案求解最优比率问题

01分数规划这个名字，第一次听说时容易觉得是某种高深的数学分支，其实它处理的问题非常朴素：在一组候选方案里，挑出“收益除以代价”最大的那个组合。我最早是在给A同学讲一套模拟项目X的建模题时认真梳理这个工具，后来发现算法竞赛里的最优比率生成树、最优比率环、最大密度子图，本质上都共享同一套“二分答案 + 判定子问题”的骨架。这篇文章适合算法竞赛选手、图论模型学习者，也适合那些需要在推荐系统、网络分析、成本优化里做“性价比最大化”的开发者。读完你不仅能看懂别人的题解，还能自己写出稳定的二分实现和迭代实现。

1. 01分数规划到底在做什么

1.1 从一个最简单的取舍问题说起

先看一个最直白的场景：你面前有 n 件物品，第 i 件物品有一个收益 a_i，一个代价 b_i，现在你可以决定每件物品选或者不选，目标是让“总收益除以总代价”最大。写成数学表达式就是：

[ \max \frac{\sum_{i=1}^{n} a_i y_i}{\sum_{i=1}^{n} b_i y_i}, \quad y_i \in {0,1} ]

你可能会想，这还不简单？每件物品算一下性价比 a_i / b_i，从高到低选不就行了？可惜大多数情况下不行。因为最终的分母是所有被选物品代价之和，并不是每个物品的代价独立固定，当你往集合里多加入一件物品时，分子和分母同时变化，原来某个物品的“单独性价比”会被整体稀释或者放大。生活里的例子是买水果：有的水果贵但特别好吃，有的便宜但一般，你要是单看单位价格的满足感，可能会一直挑便宜货，但混搭之后总满足感与总花费的比例，并不等同于简单加权排序的结果。

这类问题看起来像背包，但又不一样。背包问题是选一堆物品让总收益最大，有容量约束；这里没有容量约束，或者约束条件换成了“选出来的集合必须满足某种结构”，比如构成一棵生成树、构成一个环、构成一个子图。目标始终是比值。由于分子分母耦合，它不能直接做线性优化，于是需要把“比值目标”拆开处理。

1.2 数学化的定义与二分思想

01分数规划的标准解法，核心是把一个问题拆成两层。外层枚举一个候选答案 x，内层检查“是否存在一个合法选择，使得总收益与总代价之比能达到 x”。

这个检查可以做个恒等变形。假设所有 b_i 都是正数，那么

[ \frac{\sum a_i y_i}{\sum b_i y_i} \ge x ]

等价于

[ \sum a_i y_i - x \sum b_i y_i \ge 0 ]

也就是

[ \sum (a_i - x b_i) y_i \ge 0 ]

这样一来，给定 x 之后，每件物品的“价值”就变成了一个普通数字 d_i(x) = a_i - x b_i，内层问题就从“优化一个比值”退化成了“优化这些 d_i 的和是否非负”。如果存在一个合法集合让 d_i 的和大于等于 0，说明真实最大比值至少是 x；如果所有合法集合的 d_i 之和都小于 0，说明真实最大比值不到 x。

二分之所以能成立，是因为判断结果关于 x 单调：x 越大，d_i 越小，合法集合的和就越难大于等于 0。所以我们可以在答案范围内不断尝试 x，缩小区间，最终逼近真实最大比值。这个“给定答案，把比值判定转成普通线性判定”的思路，是整篇文章最重要的基石。

1.3 为什么叫“01”分数规划

名字里的“01”指的是决策变量 y_i 只能取 0 或 1，表示“不选”和“选”。这个约束是组合性质的来源。如果允许 y_i 在 [0,1] 区间内连续取值，那问题会变成连续最优化，通常可以用线性规划直接求解；但在生成树、环、子图这类结构约束下，只有 0/1 决策才有实际意义。

另一个容易踩的误区是，有人以为“01分数规划”的意思是物品价值必须是 0 或 1。不是这样。价值 a_i、代价 b_i 可以是任意实数，但“选择状态”是二值的。比如最优比率生成树中，每条候选边的选与不选是 0/1 变量；边的收益和成本可以是任意实数。明白这一点，再看后面的模型就不会被名字绕晕。

2. 各种经典模型和使用场景

2.1 最优比率生成树：修路问题里的性价比

假设某片区域要铺设通信网络，候选线路有 m 条，第 i 条线路的建设成本是 cost_i，建成后带来的网络价值是 value_i。现在要选 n-1 条边让所有节点连通，同时希望“总价值 / 总成本”最大。这就是最优比率生成树问题。

二分答案 x 之后，每条边的权值变成 value_i - x * cost_i。因为任何一棵生成树的边数都是固定的 n-1，所以“让总价值 / 总成本 ≥ x”等价于“存在一棵生成树，使边权和 ≥ 0”。进一步地，由于分母、边数固定，我们只需要求最大生成树，看最大权值和是否非负。

这里有个容易忽略的细节：如果目标是“总成本 / 总价值”最小，也就是修路时希望每单位价值花最少的钱，那二分判定会变成“是否存在生成树让 ∑(cost_i - x * value_i) ≤ 0”，内层则求最小生成树，看最小权值和是否小于等于 0。本质上就是把分子分母换一下，判定式调整符号，其他逻辑一模一样。

最优比率生成树在通信网络规划、电路布线、物流运输里都能见到，属于分数规划和图论结合最自然的入门模型。做题时一旦看到“选择若干条边形成生成树，最大化某种收益/成本比”，基本可以直接往这个方向套。

2.2 最优比率环：炒股、交易与判负环

再看一个更有意思的模型。有向图里每条边代表一次兑换操作，比如从货币 A 兑换到货币 B，边权表示净收益 e_i 和手续费 c_i。现在想找一条有向环，让环上的总收益与总成本之比最大，也就是问存不存在一个“高性价比”的交易循环。

二分答案 x 后，判定问题变成：是否存在有向环，使得环上边的 e_i - x * c_i 之和大于等于 0。这等价于在图中查找正环。查找正环最常用的办法是把每条边的权值取相反数，变成判断负环，然后用 Bellman-Ford 或 SPFA 检测。

我在实际写这类代码时吃过一次亏：如果图本身不连通，而我只从一个点出发做 SPFA，很容易漏掉其他连通分量里的环。解决办法是初始化时把所有点都加入队列，或者建一个虚拟源点，让 SPFA 可以从任意位置开始。检测负环时，SPFA 里记录每个点的入队次数，一旦某个点入队次数超过顶点数 n，就可以判定存在负环。这种方法的正确性依赖理论保证，但浮点误差可能让边界情况变得模糊，所以后面会专门讲精度处理。

最优比率环不仅在货币兑换里有应用，在很多“循环投入产出比”的场景中都会出现。比如某种闭环生产流程，给定每个环节的投入和产出，判断是否存在一个循环能带来超额收益，本质上也是这个模型。

2.3 最大密度子图：从社交网络到生物信息学

给定一张无向图，选出一些顶点，让“子图内部边数 / 子图顶点数”最大。这个问题叫最大密度子图。它在社区发现中很常见，因为社区通常表现为内部连接密集、外部连接稀疏的顶点集合；在生物信息学里，从蛋白质相互作用网络里找功能模块，也经常用这个目标。

用分数规划处理时，二分答案 g，判定是否存在一个顶点集合 S，使得：

[ |E(S)| - g |S| \ge 0 ]

其中 E(S) 是 S 内部的边数。从图论建模的角度，可以把每个顶点看成有一个成本 g，每条边看成有一份收益 1，问题转化为最大化“边收益 - 点成本”。这种目标可以通过构造最小割模型求解。核心思路是：把每条边设为一个额外节点，边节点与两个端点顶点连无限大容量边，然后端点顶点与源/汇连接，用最大流最小割的方式判断是否存在收益大于成本的闭合子图。

最大密度子图的代码量比生成树大不少，因为它要写网络流，很多人第一次做会觉得跨度很大。但从分数规划的角度看，外层二分逻辑完全一样，内层从“求一棵树”换成“求最小割”而已。这也再次说明：掌握分数规划的关键不是背代码，而是学会把各种组合结构统一成“给定 x，求 Σ(a_i - x b_i) 的最大值”。

2.4 分数背包与更多边角应用

网上搜“分数背包”，经常会看到另一种问题：物品可以按比例拆分，直接按单位价值排序就能得到最优解。那种问题在算法课上属于贪心入门，因为决策变量连续，不需要二分。真正和 01 分数规划密切相关的变体是“带选择数量上限”的版本。比如要求恰好选 k 件物品，最大化收益/成本比。这时给定 x，判定式变成“选 d_i = a_i - x b_i 最大的 k 件，看它们的和是否非负”。因为选择数量固定，直接排序取前 k 个即可，复杂度很低。

除此之外，很多机器学习里的评价指标优化也可以套这个框架。比如最大化 F1 分数，本质上是在精确率和召回率之间做一个调和平均，不是一个简单的线性目标；但当你把 F1 视为一个比值型指标时，可以通过参数搜索的方式，把每个阈值下的判断问题转化成带权分类损失的最小化。这种用法比竞赛图论模型更贴近工程实践。

我个人还见过有人用 01 分数规划做推荐系统的“点击率 / 曝光成本”排序。在给定收益和成本的情况下，希望选出一组候选物品让整体 ROI 最大。这时“选或不选”正是 0/1 决策，约束可能是总曝光量不超过上限，内层判定是 0/1 背包。虽然复杂度上会有点吃力，但建模思路是完全一致的。

3. 二分法 vs Dinkelbach迭代

3.1 二分答案的完整流程

二分法的实现框架非常统一，写熟之后几乎不用动脑子。步骤如下：

1. 确定答案上下界 low 和 high。如果 a_i、b_i 都是正数，任意方案的整体比率是所有单项比率的加权平均，所以答案不会超过 max(a_i / b_i)，也不会低于 min(a_i / b_i)。
2. 每次取 mid = (low + high) / 2。
3. 对 mid 构造判定式 d_i = a_i - mid * b_i，跑内层算法，求该结构下 d_i 和的最大值。
4. 如果最大值大于等于 0，说明存在方案使真实比值不少于 mid，更新 low = mid；否则更新 high = mid。
5. 重复足够多次，输出 low 或 mid。

这里有一个新手常犯的错误：内层不是判断“是否存在一个可行解满足条件”就够了，而是要解出“在给定 x 下的最优值是否大于等于 0”。因为在很多图论问题里，随便找一个可行解可能让 d_i 的和很小，但最优解却能为正。比如生成树问题里，每棵树的边数相同，但选择的边不同会导致权值和差异很大；如果只用贪心找“某棵树”判断，可能漏掉最优树。内层算法必须是在当前 x 下求这个结构里所有合法方案的最大权值和，然后拿最大值和 0 比较。

3.2 Dinkelbach迭代的思路

除了二分，还有一种经典迭代法叫 Dinkelbach。它不通过区间逼近，而是不断用当前最优解的真实比值去更新候选答案。算法流程是：

1. 随便给一个起始值 x_0，通常取 0 或某个可行方案的真实比值。
2. 用当前 x 构造 d_i = a_i - x b_i，求解内层优化问题，得到最优决策 y^，并记录该决策对应的实际比值 r = Σ a_i y_i^/ Σ b_i y_i^*。
3. 令新的 x = r，重复计算，直到相邻两轮 x 的差值小于 eps，或者判定式的最优值接近 0。

Dinkelbach 的优势在于，它收敛时得到的不只是一个区间，而是会精确落在最优解对应的比值上。在不少问题上，迭代次数比二分的几十轮更少。但它有个隐含要求：内层算法必须能够返回“最优解”本身，而不仅仅是“是否存在可行解”。对于最大生成树、背包这类能直接记录方案的算法没问题；但对于 SPFA 判负环，往往只能返回“有环”还是“没环”，拿不到精确的最优解，这时候 Dinkelbach 就用不了。

3.3 两种实现怎么选

没有绝对的好坏，我的选择习惯是看内层求解器能给出什么信息。如果内层返回的是最优解，Dinkelbach 往往更优雅；如果内层只能做可行性判断，那就用二分。

在算法竞赛里，我更推荐二分法。因为 SPFA 判负环、最小割这些内层实现本身就有不少浮点误差，Dinkelbach 对“最优解”的依赖会让误差更难排查；而二分法固定迭代 60 次或 100 次，逻辑简单，赛后调起来也方便。在离线数据分析里，如果内层是一个可以直接算全局最优值的凸优化函数，Dinkelbach 会让整体迭代次数少很多。

4. 从零写一个可复现的代码

4.1 题目抽象与输入约定

为了把两种方法都演示清楚，我选一个最简单的模型：给定 n 件物品，每件有收益 a_i 和代价 b_i，要求至少选择一件，最大化总收益/总代价。这个模型没有额外的结构约束，内层判定就是“选哪些物品能让 d_i 的和最大”。

输入格式说明：第一行一个整数 n，第二行 n 个浮点数表示 a_i，第三行 n 个浮点数表示 b_i。保证 b_i > 0，且目标答案为正。

这个简单模型能直观展示二分和 Dinkelbach 的代码骨架。理解了以后，把它换成生成树、环、子图时，只需要替换内层函数，外层逻辑完全不用动。

4.2 二分法参考实现（C++）

先看二分法。我习惯固定迭代 100 次，而不是用while (high - low > eps)，因为上下界范围可能很大，如果 eps 设置不合理，可能陷入死循环或者精度不够。固定迭代次数可以完全避免这个问题。

#include <bits/stdc++.h> using namespace std; int n; vector<double> a, b; // 判断是否存在选择方案使得 sum(a_i - x * b_i) >= 0 bool check(double x) { double sum = 0; for (int i = 0; i < n; i++) { double d = a[i] - x * b[i]; if (d > 0) sum += d; } // 因为需要至少选一件，如果全是非正项，就选最大的一项 if (sum == 0) { double mx = -1e18; for (int i = 0; i < n; i++) { mx = max(mx, a[i] - x * b[i]); } sum = mx; } return sum >= 0; } int main() { cin >> n; a.resize(n); b.resize(n); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; double low = 0, high = 0; for (int i = 0; i < n; i++) high = max(high, a[i] / b[i]); for (int iter = 0; iter < 100; iter++) { double mid = (low + high) / 2; if (check(mid)) low = mid; else high = mid; } cout << fixed << setprecision(10) << low << "\n"; return 0; }

这个实现有一个细节值得说明：为什么内层判断d > 0就选中？因为在没有任何结构约束时，所有 d_i 为正的物品加入集合只会让总和变大；d_i 为 0 的物品加不加不影响总和，但为了保证至少选一件，需要单独处理全非正的情况。这里的sum == 0判断在浮点运算里其实不够严谨，稳妥做法是用一个标志位记录是否选中过物品，或者直接取所有负值里最大的一项作为保底方案。

4.3 Dinkelbach参考实现（Python）

再看 Dinkelbach 版本。它的内层也需要求解“最优选择和”，但除此之外还要记录当前最优方案对应的真实比值。在这个简单无约束模型里，最优方案仍然是所有 d_i > 0 的物品集合，遇到全负的情况则选最大的一项。

n = int(input()) a = list(map(float, input().split())) b = list(map(float, input().split())) x = 0.0 for _ in range(100): d = [a[i] - x * b[i] for i in range(n)] selected = [i for i in range(n) if d[i] > 0] if not selected: selected = [max(range(n), key=lambda i: d[i])] sum_a = sum(a[i] for i in selected) sum_b = sum(b[i] for i in selected) new_x = sum_a / sum_b if abs(new_x - x) < 1e-10: x = new_x break x = new_x print(f"{x:.10f}")

停止条件我用的是相邻两轮new_x和x的差小于 1e-10。理论上 Dinkelbach 的收敛速度很快，但对浮点误差敏感，所以轮数上限设成 100 只是保险。如果你发现结果抖动，可以观察每一轮 x 的变化，往往会看到先快速上升，然后在一个小范围内浮动，这时把停止阈值放宽一些即可。

4.4 边界测试与参数调整

写完之后一定要跑几组边界数据。我先用一个手工能算的用例：

• n = 3
• a = [2, 3, 1]
• b = [1, 2, 1]

枚举所有非空选择：选第 1 件比值为 2，选第 2 件比值为 1.5，选第 3 件比值为 1，选第 1 和第 2 件比值为 5/3≈1.6667，选第 1 和第 3 件为 1.5，选第 2 和第 3 件为 4/3≈1.3333，选全部为 6/4=1.5。所以最优结果是 5/3。两个程序输出都应该接近 1.6666666667。

再测一个边界：n=1, a=0, b=1，答案应该是 0。因为 d_i 全非正，保底方案选这一件，new_x = 0 / 1 = 0。二分下界设为 0，正确输出 0。

还有一个容易踩的坑是大数值。如果 a 和 b 都在 1e9 级别，二分的 high 是 1e9 量级，迭代 100 次能缩到 1e-21 量级，对 double 来说足够了。但如果在内层用int存 d_i 的累加和，很容易溢出，必须用double。

5. 常见坑与排查实录

5.1 EPS到底怎么选

这是被问得最多的一个问题。很多人习惯const double eps = 1e-6，但输出要求保留三位小数时，这个精度其实够；保留六位或更多时，1e-6 作为二分停止条件就危险了。因为二分的过程中，low 和 high 之间可能还残留着 1e-6 的差距，输出 mid 时最后一位已经不可靠。

我的建议是，能用固定迭代次数就别纠结 eps。二分区间从 0 到 1e9，迭代 100 次，区间长度大约变成 1e9 / 2^100，远小于 double 精度上限。如果一定要用 while 循环，停止条件写high - low > 1e-12会稳妥很多。别忘了浮点运算本身有舍入误差，不要在内层用== 0做判断，而是用一个极小的正数1e-12作为容差。

5.2 二分上限和下限怎么取

我见过不少人把上限直接写成1e18，然后迭代次数只写 30 次，结果误差巨大。另一个常见问题是下界设成 0，但如果答案是负数，二分永远不成立。幸好大多数标准模型里 a_i、b_i 都为正，答案也正，0 作为下界没问题。

更稳妥的做法是从单项比率里取上下界。因为任意方案的比值都是所选物品单项比率的加权平均，所以答案一定在min(a_i/b_i)到max(a_i/b_i)之间。这样二分区间更紧凑，同样迭代次数下精度更高。如果遇到收益或代价可能为负的情况，这种取法就不一定成立，需要重新推导可行域，但竞赛题里绝大多数都是正数模型。

5.3 图模型里判负环的细节

最优比率环的判定是最容易翻车的场景。使用 SPFA 判负环时，有几点经验：

• 初始化时要把所有点都加入队列，否则不连通图里的环检测不到。
• 记录每个点的入队次数，超过顶点总数 n 就认为存在负环。注意这个阈值在理论上可以再优化，但 n 是安全选择。
• 浮点情况下，边权可能非常接近 0，导致正常算法认为没有负环但实际上有。此时可以给比较运算加一个小偏移，例如判断dist[v] > dist[u] + w + 1e-12才做松弛，防止抖动。
• 如果超时，可以限制 SPFA 的总松弛次数，比如当总次数超过 n * 边数 的某个倍数时直接判定有环。这个技巧不保证绝对正确，但实际效果很好。

有一次排查一个比率环代码，发现结果和标准答案差在小数点后第 5 位，最后定位到是 SPFA 里用int存了边权，浮点部分被截断。所以图模型里的判环代码，一定要用double或long double全程计算，不能中途转整数。

5.4 浮点比较与输出陷阱

我踩过最深的坑是输出。C++ 的cout默认精度只有 6 位有效数字，输出 0.123456789 会变成 0.123457，看起来好像差不多，但对拍时会一直 WA。必须显式写cout << fixed << setprecision(10)或者用printf("%.10f")。Python 的print默认精度倒是不错，但格式化输出时也要注意保留位数。

内层判定里的浮点比较同样要小心。比如生成树求出的最大边权和是 1e-11，理论上它大于 0，但由于浮点误差可能变成 -1e-12，导致二分方向判断错误。我一般会在 check 函数里加上容差：return sum >= -1e-12。这个容差不能太大，否则会把真正不满足条件的 mid 误判为可行，导致最终答案偏大。

6. 一些个人经验和小技巧

6.1 从“会写题”到“会建模”的跨越

很多 A 同学拿着分数规划的题，第一步就卡住：看出来了是比率目标，但不知道内层该用什么算法。我的经验是，拿到任何“最大化 A/B”的题，先问自己一句：“如果我已经知道答案是 x，能不能快速验证？”验证通常比直接求解容易得多。生成树用最大生成树验证，环用判环验证，子图用最小割验证，剩下的交给二分。这个“验证优先”的思路不仅适用于分数规划，也适用很多二分答案类问题。

慢慢你会发现，所有 01 分数规划的题解都可以套同一个壳：

• 外层：二分 x 或 Dinkelbach 迭代；
• 内层：在当前 x 下把每条边/物品的权值改成 d_i，然后在约束结构里求权值和的极值，与 0 比较。

把这个壳写熟了，遇到新题时你要做的就只有一件事：设计内层算法。

6.2 01分数规划和01背包、参数搜索的关系

如果你写过 01 背包，再来看分数规划，会有一种微妙的重合感。给定 x 后，每个物品的价值变成 d_i = a_i - x b_i，如果有容量约束，内层就是一个 01 背包。外层二分 x，内层跑背包，这是“分数规划 + 背包”的常见组合。而如果只是选择任意集合，内层退化成“选正数项求和”，连背包都不用。

从更高的视角看，二分 x 本质上是参数搜索。我们有一个参数 x，用它把非线性目标“拉直”成线性目标，然后通过单调性收敛。Dinkelbach 也是参数搜索，只不过参数更新的方式更聪明。我在做推荐系统的 ROI 排序时，也会用类似思路：先假设一个 ROI 阈值，把所有候选项按收益减成本*阈值排序，再从高到低选；然后更新阈值，反复迭代。

6.3 后续可以再深入的几个方向

如果这篇文章让你对 01 分数规划产生了兴趣，有几个方向值得继续探索。

第一是凸优化视角。01 分数规划本质上是在优化一个拟凸函数，目标函数的水平集是凸的，这解释了为什么二分和 Dinkelbach 都有效。第二是网络流结合，最大密度子图的最小割建模思路可以推广到带权图、带点权图，甚至边权和点权同时存在的场景。第三是多目标比率规划，同时优化两个或更多比值的难度会大幅上升，通常只能用近似算法或帕累托方法。第四是动态规划的结合，当 n 较小但选择有先后顺序时，可以在二分内部跑二维 DP，比如另一个经典问题“最优比率路径”。

这些方向我现在还在慢慢啃，但掌握基础以后，再读相关论文和题解会流畅很多。

最后分享一点自己的体会。我最初写最优比率环时，连续几个晚上都在调 SPFA 的浮点精度，后来换成了“固定迭代轮数 + 更宽松的容差”，问题立刻消失。如果你也准备上手这个主题，建议先不要碰图论模型，老老实实把最简单的无约束选择问题用二分和 Dinkelbach 各写一遍，再用随机数据对拍。等代码骨架完全变成肌肉记忆，再挑战生成树和判负环，会轻松得多。这个工具的适用范围很广，从竞赛题到工程里的性价比优化都能碰到，值得花时间彻底弄懂。