0/1 分数规划
n n n 个物品选 k k k 个使 Σ a i Σ b i \frac{\Sigma a_i}{\Sigma b_i} ΣbiΣai 的值最大化。
设答案为 a n s ans ans，某一比值为 P P P（均为浮点数，小数点后保留位数见题面）。
作为答案——一个最大值，需要满足的条件就一定是
P
≤
a
n
s
P \le ans
P≤ans。（没有争议吧，不然就能更新最大值了）。
那么把上面的不等式做一点小操作：
P ≤ Σ a i Σ b i 即 P ∗ Σ b i ≤ Σ a i 也就是 Σ ( a i − P ∗ b i ) ≥ 0 P \le \frac{\Sigma a_i}{\Sigma b_i} \\ 即 P*\Sigma b_i \le \Sigma a_i \\ 也就是 \Sigma (a_i - P * b_i) \ge 0 P≤ΣbiΣai即P∗Σbi≤Σai也就是Σ(ai−P∗bi)≥0
其实这就是一个判断答案的式子。。
浮点数二分答案，判断就是 Σ ( a i − P ∗ b i ) ≥ 0 \Sigma (a_i - P * b_i) \ge 0 Σ(ai−P∗bi)≥0，细节略。