01分数规划

发表于 2020-10-03 分类于 OI & ACM 阅读次数：

本文字数： 175 阅读时长 ≈ 1 分钟

简介

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

有一堆物品，每个物品有价值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$