0x00 背景
求 :
\(max\tfrac{\sum_{i=1}^na_ix_i}{\sum_{i=1}^nb_ix_i}(x_i=0/1)\)
我们称此类问题为 “0/1分数规划”
Plan A
爆搜 , 时间复杂度 \(2^n\) , 寄
Plan B
二分法
0x01 二分法和0/1分数规划
part 1 怎么想到的 ?
我们先构造一个式子 : \(\sum_{i=1}^n(a_i-L*b_i)*x_i\ge0\)
我们不妨随便猜测一个值 \(L\) , 考虑是否存在一组解 \(\{x_1,x_2,...,x_n\}\) 满足上式
- 若存在一组解 , 那么变形得 \((\sum_{i=1}^na_ix_i)-L*(\sum_{i=1}^nb_ix_i)\ge0\) , 进一步地 :
\(存在\{x_1,x_2,...,x_n\}使得\tfrac{\sum_{i=1}^na_ix_i}{\sum_{i=1}^nb_ix_i}\ge L\)
也就是说 , \(L\)比我们要求的最大值小
- 若不存在 , 那么 :
\(对于所有\{x_1,x_2,...,x_n\} , \tfrac{\sum_{i=1}^na_ix_i}{\sum_{i=1}^nb_ix_i}< L\)
也就是说 , \(L\)比我们要求的最大值小
显然 , 我们求答案的过程是满足单调性的 , 满足使用二分进行求解的要求 , 因此是可以考虑使用二分求解的
part 2 怎么做的?
我们二分 \(L\) 的时候如何进行 \(check\) 呢 ?
上面最容易验证的就是\(\sum_{i=1}^n(a_i-L*b_i)*x_i\ge0\) 了 , 验证的方法非常简单 , 只需要从那些\((a_i-L*b_i)\) 能中选出正数即可
二分结束 , \(L\)即为我们需要的解
标签：分数,ix,ge0,na,sum,二分,规划,nb From： https://www.cnblogs.com/sheepcsy/p/16877988.html