01分数规划的学习笔记 QAQ
感觉没什么用啊……
处理一类选点取max问题
通俗的讲就是令 \(m\) 个 \(k_i = 1\) 其余是 0
然后使得 \(\sum \frac{a_i * k_i}{b_i * k_i}\) 最大
做法大概就是
\(\sum \frac{a_i * k_i}{b_i * k_i} >= mid\)
然后移一个项
\(\sum a_i * k_i - \sum b_i * k_i * mid >= 0\)
则 \(mid\) 可行
然后二分，没了。
原文：https://www.cnblogs.com/Isaunoya/p/12198605.html