本文共 1659 字，大约阅读时间需要 5 分钟。

理解什么是01分数规划

首先先分开看一下三个关键词：01、分数、规划

这类题一般是给一堆a[i]和一堆b[i]，这两个是有联系的，比如第i个物品的收益是a[i]，花费是b[i]，问选择哪k个物品使得$\frac{{\sum }_{选出来的a[i]}}{{\sum }_{选出来的b[i]}}$最大，也就是求选出来的平均性价比最高。

1、那么01指的什么呢？

我们可以这么理解，对于这n个数，每个数我们有两种抉择，选他或者不选他，选用1表示，不选用0表示，然后我们用一个c[i]数组代表我们对第i个物品选还是不选。那么我们的函数可以写成$\sum \frac{a[i]\times w[i]}{b[i]\times w[i]}$。 2、分数指的什么呢？ 分数就是这类问题的求的答案形式是一个分数 3、而规划就是指我们要规划一个选择，使得答案最小，就是一个最小化的选择。

---

01分数规划的做法

我们已经理解了01分数规划这类问题是什么了，那么如何做呢？我们先可以假设计算的答案是ans，则有$$ans\le \sum \frac{a[i]\times w[i]}{b[i]\times w[i]}$$我们对这个函数计算式进行化简，并求出ans的最大值就等于$\sum \frac{a[i]\times w[i]}{b[i]\times w[i]}$。

$$ans\times \sum b[i]\times w[i]\le \sum a[i]\times w[i]$$ $$\sum a[i]\times w[i]-ans\times \sum b[i]\times w[i]\ge 0$$ $$w[i]\times \sum a[i]-ans\times b[i]\ge 0$$ 根据上式，我们只需要判断选出来的$\sum a[i]-ans\times b[i]$是否大于等于0即可，那么我们还有两个问题：1、如何选择呢？2、ans是多少呢？对于1，我们可以计算出$a[i]-ans\times b[i]$的值，排个序，取前k个就能保证这个值最大，然后我们计算前k个的和是否大于等于0。那么ans呢，二分啊，明显的，如果ans变大，则$a[i]-ans\times b[i]$就会变小，ans和函数值是单调对应关系，符合二分的特征，所以问题就解决了。

---

常见模型

1、01规划

裸01规划

例题：

2、01规划与最小生成树

最优比率生成树

例题：

3、01规划与环

最优比率生成环

例题：

4、01规划与网络流

最优比率最小割

例题： 题解：

转载地址：http://rfbki.baihongyu.com/