# 0/1分数规划学习笔记
——by sunzz3183
------------
## 介绍
$0/1$ 分数规划是指，给定整数 $a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_n$，求一组解 $x_i,x_i \in \left \{ 0,1 \right \} $，使下面的式子最大化：
$$
\frac{\sum_{i=1}^{n} a_i\times x_i}{\sum_{i=1}^{n} b_i\times x_i}
$$
## 求法
我们设一个值 $L$，假设存在一组解使得：
$$
\frac{\sum_{i=1}^{n} a_i\times x_i}{\sum_{i=1}^{n} b_i\times x_i} \geq L
$$
那么此时显然，最大值大于 $L$。
又因为
$$
\begin{aligned}
\frac{\sum_{i=1}^{n} a_i\times x_i}{\sum_{i=1}^{n} b_i\times x_i} &\geq L\\
\sum_{i=1}^{n} a_i\times x_i&\geq L\times \sum_{i=1}^{n} b_i\times x_i\\
\sum_{i=1}^{n} a_i\times x_i-L\times \sum_{i=1}^{n} b_i\times x_i&\geq 0\\
\sum_{i=1}^{n} (a_i-L\times b_i)\times x_i&\geq 0
\end{aligned}
$$
所以，
假设存在一组解使得：
$$ \sum_{i=1}^{n} (a_i-L\times b_i)\times x_i\geq 0 $$
那么此时最大值大于等于 $L$。
同理
假设任意一组解使得：
$$ \sum_{i=1}^{n} (a_i-L\times b_i)\times x_i<0 $$
那么此时最大值小于 $L$。
又显然，$L$ 在取值时，解的存在满足单调性，所以显然可以二分。