今天碰到了一道神题，想了很久都没想出来，看了题解才知道要用01分数规划，然而我太弱了并不知道这是什么东西……
于是专门学习了一下01分数规划，发现真是个神奇的东西……
01分数规划是指这样一类问题：给出两个长度为n的序列a和b，设$R=\large{\frac{\sum_{i=1}^{n}{a_i\times x_i}}{\sum_{i=1}^{n}{b_i\times x_i}}\left(x_i\in 0,1\right)}$，要最大化或最小化R。
这类问题是有通用的解法的。
对原式进行简单的变形，得
$f\left( R\right)=\sum_{i=1}^{n}{a_i\times x_i}-R\times\sum_{i=1}^{n}{b_i\times x_i}$
$\Rightarrow f\left( R\right)=\sum_{i=1}^{n}{\left( a_i-R\times b_i\right) \times x_i}$
这个方程具有单调性，所以可以用二分法求解。以求最大值为例，每二分出一个mid，若存在一组$x_i$，使得$f\left( R\right) >0$，就说明R还可以更大。
评论 (0)
