问题

$$
求一组解x_1,x_2,x_3,x_4…x_n,x=0\ or \ 1\
使得\frac{\sum_{i=1}^{n}a_i\times x_i}{\sum_{i=1}^{n}b_i\times x_i}最大化或最小化
$$

解决

总体思路:通过假设存在某种形式(比当前值大或小)的解,然后寻找这些数之间的不等关系从而简化问题
考虑随机一个L,然后假设

$$
存在{x_1,x_2…x_n},使得\
\frac{\sum_{i=1}^{n}a_i\times x_i}{\sum_{i=1}^{n}b_i\times x_i}>=L
$$

然后化简这个式子:

$$==>$$

$$
\frac{a_1x_1+a_2x_2+a_3x_3+…+a_nx_n}{b_1x_1+b_2x_2+b_3x_3+…+b_nx_n}>=L
$$

$$==>$$

$$
a_1x_1+a_2x_2+a_3x_3+…+a_nx_n>=L*(b_1x_1+b_2x_2+b_3x_3+…+b_nx_n)
$$

$$==>$$

$$
a_1x_1-L\times b_1x_1+a_2x_2-L\times b_2x_2+…+a_nx_n-L\times b_nx_n>=0
$$

$$==>$$

$$
\sum_{i=1}^{n}a_i x_i-L\times b_ix_i>=0
$$

也就是说,如果如果可以构造出一组解使得

$$
\sum_{i=1}^{n}(a_i-L\times b_i)x_i>=0
$$

那么我们当前随机的这个L比原式的最大值要小,即

$$
存在{x_1,x_2…x_n},使得\
\frac{\sum_{i=1}^{n}a_i\times x_i}{\sum_{i=1}^{n}b_i\times x_i}>=L
$$

同理,如果构造不出一组解x满足上式,也就是说对于任意的一组解x都有:

$$
\sum_{i=1}^{n}(a_i-L\times b_i)x_i<0
$$

那么我们随机的这个数比最大值要大即

$$
任意{x_1,x_2…x_n},使得\
\frac{\sum_{i=1}^{n}a_i\times x_i}{\sum_{i=1}^{n}b_i\times x_i}<L
$$

根据定理:判定问题普遍比最优问题简单,这种转化是有意义的

具体来讲就是上式中的$a_i-L\times b_i$是可以O(1)算出来的,那么这个问题就相当于是在一堆数中让你选出来一些数然后求这些数的和的最大值,显然直接贪心把所有正数拿出来就好了啊

很显然,这个式子$\sum_{i=1}^{n}(a_i-L\times b_i)x_i$关于L单调,也就是说,L越大,这个式子的最优解越小,在0处为最优解

而单调性是利用二分解决问题的重要前提

上面的问题(求最大值)仅仅提供一个思维导向,因为很多题可以问你最小值,具体推理不再展开,但思路是一样的: