分数规划

引入

分数规划主要是对形如
$$\frac{\sum _{i=1}^n{a}_i\ast w_i}{\sum _{i=1}^n{b}_i\ast w_i}$$
\(w\)数组表示选与不选，最值化上式，不过一般会要求选k个，或者总重量至少为\(W\)再加上一大堆乱七八糟的限制
——————————————————————

解决方法

一般来讲用二分法，还有一个\(Dinkelbach\) 算法算是对二分的优化，就是用上一次的答案来做左边界，不过我们没有必要学习它

P10505
在这可以写一下分数规划的基本原理
\(\frac{a}{b}>mid\Longrightarrow a-b*mid>0\)
找所有大于0的元素对累加即可
基本上所有的分数规划都是这个原理，而这个题让我们选择\(n-k\)个数，如果必须要选择负数那怎么办呢，考虑此时还满足相加吗，实际上是满足的（在\(mid<1\)时），读者感兴趣可以自己去证明

那这题式子很显然就是\(设 t_i=a_i-mid*b_i,取最大的几个即可\)

P4377