01分数规划

算法概念

给定一些二元组 $(si，pi)$，从中选取一些二元组，使得 $\frac{∑s_i}{∑p_i}$ 最大（最小）。

解决流程

第一步, 二分答案，转化成存在性问题。

第二步, 转换题目公式，例如运用找负环（正环）、找固定差值等方法进行判断。

题目结合

【例题】观光奶牛

设置 二分分界点 为 $mid$, 则原题题意转为判断 $\frac{∑f_i}{∑p_i} >= mid$ 是否正确

以下是等价变形 ：

$\frac{∑f_i}{∑p_i} >= mid$

=> $∑f_i >= mid * ∑p_i$

=>$∑f_i - mid * ∑p_i >= 0$

=>$∑_{f_i - mid * p_i} >= 0$

=> 判断是否存在负环

【习题】单词环