何为01分数规划

01分数规划解决的是这么一类问题：

从给定的数列 a i 、 b i {a_i}、{b_i} ai、bi，求 ∑ i = 1 a i ∗ p i ∑ i = 1 b i ∗ p i \frac{\sum_{i=1}{a_i}*p_i}{\sum_{i=1}{b_i}*p_i} ∑i=1bi∗pi∑i=1ai∗pi的最值问题

其中p为一个01数列。

也就是从一个二元组列表中选一些二元组，求x项之和/y项和的最值。

常常是求最大中的最小、最小中的最大。

这类问题我们通常用二分+分数规划来做

详解

直接求解不容易，我们可以考虑如何判断某个答案是否合法。

下面以最小值为例：

假设二分出答案ans

令 ∑ i = 1 a i ∗ p i ∑ i = 1 b i ∗ p i \frac{\sum_{i=1}{a_i}*p_i}{\sum_{i=1}{b_i}*p_i} ∑i=1bi∗pi∑i=1ai∗pi中分母为A，分子为B

那么 = A / B > = a n s =A/B >= ans =A/B>=ans

= A > = a n s ∗ B =A>=ans*B =A>=ans∗B

= A − B ∗ a n s > = 0 =A-B*ans>=0 =A−B∗ans>=0

把AB两个式子展开：

= ∑ i = 1 a i ∗ p i − b i ∗ p i ∗ a n s > = 0 =\sum_{i=1}^{a_i*p_i-b_i*p_i*ans}>=0 =∑i=1ai∗pi−bi∗pi∗ans>=0

所以当最后一个式子成立的时候答案ans合法。

我们有注意到ans越大越不好满足，所以这个是有单调性的。

如果ans不行，那么比ans大的都不能满足；如果ans合法，那么比ans小的都合法。

因此我们可以二分ans，然后判断。