10.01分数规划

01分数规划

分数规划处理这样一些问题

给出 $a_{i}$ 和 $b_{i}$ ,求一组 $w_{i} \in {0, 1}$ 最小化或者最大化

\frac{\sum_{i = 1}^{n} a_{i} \times w_{i}}{\sum_{i = 1}^{n} b_{i} \times w_{i}}

求解

假设需要求最大值，那么我们二分一个答案 $m i d$

\begin{aligned} \frac{\sum_{i = 1}^{n} a_{i} \times w_{i}}{\sum_{i = 1}^{n} b_{i} \times w_{i}} > m i d \\ ⟹ & \sum_{i = 1}^{n} a_{i} \times w_{i} - m i d \times \sum_{i = 1}^{n} b_{i} \times w_{i} > 0 \\ ⟹ & \sum_{i = 1}^{n} w_{i} \times (a_{i} - m i d \times b_{i}) > 0 \end{aligned}

那么，只需要求出不等号左边的最大值就好了，如果左边的最大值大于 $0$ ，说明这个 $m i d$ 是成立的

暂时还不知道什么东西

分数规划的难点在于如何求出 $\sum_{i = 1}^{n} w_{i} \times (a_{i} - m i d \times b_{i})$ 的最大值/最小值