01分数规划

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

给出 $a_i$ 和 $b_i$ ,求一组 $w_i \in \{0,1\}$ 最小化或者最大化

$\frac{\sum\limits_{i=1}^n a_i \times w_i}{\sum\limits_{i=1}^n b_i \times w_i}$

求解

二分法

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

$\begin{aligned} &\frac{\sum\limits_{i=1}^n a_i \times w_i}{\sum\limits_{i=1}^n b_i \times w_i}>mid\\ \Longrightarrow &\sum\limits_{i=1}^n a_i \times w_i -mid \times \sum\limits_{i=1}^n b_i \times w_i >0\\ \Longrightarrow &\sum\limits_{i=1}^n w_i \times (a_i-mid \times b_i)>0 \end{aligned}$

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

Dinkelbach 算法

暂时还不知道什么东西

分数规划的难点在于如何求出 $\sum\limits_{i=1}^n w_i \times (a_i-mid \times b_i)$ 的最大值/最小值