01分数规划

Posted on 2018-11-02 Views:

题意

给定 $a_1,a_2,\cdots a_n$ 以及 $b_1,b_2,\cdots b_n$ ，要求最大化：

$\frac{\sum_{i = 1}^n a_ix_i}{\sum_{i = 1}^n b_ix_i}$

其中 $\forall 1\le i \le n, x_i \in \{0, 1\}$ 。

解法

我们可以二分答案，这样这个问题就转变为：能否求出一组解，使得 $\frac{\sum_{i = 1}^n a_ix_i}{\sum_{i = 1}^n b_ix_i} \ge L$ ？

对不等式进行变形：

$\begin{aligned} \frac{\sum_{i = 1}^n a_ix_i}{\sum_{i = 1}^n b_ix_i} &\ge L \\ \sum_{i = 1}^n a_ix_i &\ge L\sum_{i = 1}^n b_ix_i \\ \sum_{i = 1}^n a_ix_i - L\sum_{i = 1}^n b_ix_i &\ge 0 \\ \sum_{i = 1}^n (a_i - Lb_i)x_i &\ge 0 \end{aligned}$

我们计算 $\sum_{i = 1}^n (a_i - Lb_i)x_i$ 的最大值，即构造

使

当且仅当

，并判断最大值的正负性，在此基础上不断二分答案即可。时间复杂度为 $O(n\log L_{max})$ 。