0x39 0/1 分数规划

0/1分数规划模型是指，给定整数 $a_1,a_2,\dots ,a_n$ 以及 $b_{1},b_{2},\dots ,b_{n}$ ，求一组解 $x_{i}$ $(1\leq i\leq n,x_{i} = 0$ 或1)，使下式最大化：

通俗地说，就是给定 $n$ 对整数 $a_{i}, b_{i}$ ，从中选出若干对，使选出的数对的 $a$ 之和与 $b$ 之和的商最大。

我们不妨随便猜测一个值 $L$ ，然后考虑这样一个问题：是否存在一组解 $\{x_{1}, x_{2}, \dots, x_{n}\}$ 满足 $\sum_{i=1}^{n}(a_{i} - L * b_{i}) * x_{i} \geq 0$ 。

1. 如果存在一组解，使得 $\sum_{i=1}^{n}(a_i - L * b_i) * x_i \geq 0$ ，那么变形得 $(\sum_{i=1}^{n} a_i * x_i) - L * (\sum_{i=1}^{n} b_i * x_i) \geq 0$ 。进一步可知：

也就是说， $L$ 比我们求的最大值要小。

1. 如果对于任意一组解，都有 $\sum_{i=1}^{n}(a_i - L * b_i) * x_i < 0$ ，那么同理可知

也就是说， $L$ 比我们求的最大值要大。

这与“二分答案”的情形非常相似。虽然最终的答案是未知的，但是如果我们猜测一个值 $L$ ，就能通过判定“是否存在一组解满足 $\sum_{i=1}^{n}(a_i - L * b_i) * x_i \geq 0$ ”，得到 $L$ 应该变得更大还是更小。也就是说，这个 $L$ 关于“解的存在性”具有“单调性”。

如何判定“是否存在一组解满足 $\sum_{i=1}^{n}(a_i - L * b_i) * x_i \geq 0$ ”呢？我们考虑这样一个问题：给定整数 $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$ 以及 $L$ ，求一组解 $x_i$ （ $1 \leq i \leq n$ ， $x_i = 0$ 或 1），使 $\sum_{i=1}^{n}(a_i - L * b_i) * x_i$ 最大化。显然，只需判定这个最大值是否非负即可。

这个判定问题显然比原问题要简单得多——因为 $a_{i} - L * b_{i}$ 可以直接被计算出来。这就等价于从 $n$ 个数里选出若干个，使它们的和最大。把所有的正数加起来就可以了。

综上所述，我们可以二分答案（实数）。当二分的值为 $mid$ 时，我们就计算 $\sum_{i=1}^{n}(a_i - mid * b_i) * x_i$ 的最大值，检查最大值是否非负。若非负，则令 $l = mid$ ，否则令 $r = mid$ 。当二分停止时，就得到了0/1分数规划问题的解。

0x3A节的练习中包含一道0/1分数规划的基本题目。另外，许多0/1分数规划题目与图论有所结合，0x62和0x65节还会继续探讨两道0/1分数规划的例题。

除了二分法外，0/1分数规划还有一种求解方法——Dinkelbach迭代法。学有余力的读者可以自行查阅相关资料。