01分数规划

简介

大概就是最大化/最小化这么一个东西:

有一堆物品,每个物品有价值c和容量w,选择一部分物品最大化 $\frac{\sum{c_i}}{\sum{w_i}}$

我们二分最大值,然后这样判断 $\frac{\sum c_i}{\sum w_i}\ge k\Rightarrow \sum c_i-k*\sum w_i\ge 0$

例题

poj 2976 Dropping tests