分数规划模型学习笔记

问题

给定 $n$ 个二元组 $(a_i, b_i)$ ，从中选出 $k$ 个二元组使得 $\frac{\Sigma a_i}{\Sigma b_i}$ 尽可能大，求出最小值。

求解

假设

$$\frac{\Sigma a_i}{\Sigma b_i} \geq x$$

则可以将式子变形为

$$\Sigma a_i - x \cdot \Sigma b_i \geq 0$$

对 $x$ 进行二分，将 $a_i - x \cdot b_i$ 从大到小排序，选出前 $k$ 个 ，判断式子是否成立，如果成立则增加 $x$ ，不成立则减小 $x$ ，直至求出最优解。