掌握01分数规划思想+应用模型总结

我不是女神ヾ 2022-10-25 04:57 167阅读 0赞

### 理解什么是01分数规划 ###

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

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

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

--------------------

### 01分数规划的做法 ###

我们已经理解了01分数规划这类问题是什么了，那么如何做呢？我们先可以假设计算的答案是ans，则有 a n s ≤ ∑ a \[ i \] × w \[ i \] b \[ i \] × w \[ i \] ans \\le \\sum\{\\frac\{a\[i\] \\times w\[i\]\}\{b\[i\] \\times w\[i\]\}\} ans≤∑b\[i\]×w\[i\]a\[i\]×w\[i\]我们对这个函数计算式进行化简，并求出ans的最大值就等于 ∑ a \[ i \] × w \[ i \] b \[ i \] × w \[ i \] \\sum\{\\frac\{a\[i\] \\times w\[i\]\}\{b\[i\] \\times w\[i\]\}\} ∑b\[i\]×w\[i\]a\[i\]×w\[i\]。  
 a n s × ∑ b \[ i \] × w \[ i \] ≤ ∑ a \[ i \] × w \[ i \] ans \\times \\sum b\[i\] \\times w\[i\]\\le \\sum a\[i\] \\times w\[i\] ans×∑b\[i\]×w\[i\]≤∑a\[i\]×w\[i\]  
 ∑ a \[ i \] × w \[ i \] − a n s × ∑ b \[ i \] × w \[ i \] ≥ 0 \\sum a\[i\] \\times w\[i\] - ans \\times \\sum b\[i\] \\times w\[i\]\\ge 0 ∑a\[i\]×w\[i\]−ans×∑b\[i\]×w\[i\]≥0  
 w \[ i \] × ∑ a \[ i \] − a n s × b \[ i \] ≥ 0 w\[i\] \\times \\sum a\[i\] - ans \\times b\[i\] \\ge 0 w\[i\]×∑a\[i\]−ans×b\[i\]≥0  
根据上式，我们只需要判断**选出来的** ∑ a \[ i \] − a n s × b \[ i \] \\sum a\[i\] - ans \\times b\[i\] ∑a\[i\]−ans×b\[i\]是否大于等于0即可，那么我们还有两个问题：1、如何选择呢？2、ans是多少呢？对于1，我们可以计算出 a \[ i \] − a n s × b \[ i \] a\[i\] - ans \\times b\[i\] a\[i\]−ans×b\[i\]的值，排个序，取前k个就能保证这个值最大，然后我们计算前k个的和是否大于等于0。那么ans呢，二分啊，明显的，如果ans变大，则 a \[ i \] − a n s × b \[ i \] a\[i\] - ans \\times b\[i\] a\[i\]−ans×b\[i\]就会变小，ans和函数值是单调对应关系，符合二分的特征，所以问题就解决了。

--------------------

### 常见模型 ###

#### 1、01规划 ####

裸01规划  
例题：[POJ2976 Dropping tests][]

#### 2、01规划与最小生成树 ####

最优比率生成树  
例题：[POJ2728 Desert King][]

#### 3、01规划与环 ####

最优比率生成环  
例题：[P1768 天路][P1768]  
[Acwing361 观光奶牛][Acwing361]

#### 4、01规划与网络流 ####

最优比率最小割  
例题：[Acwing2279 网络战争][Acwing2279]  
**题解：**[网络战争][Link 1]

[POJ2976 Dropping tests]: http://poj.org/problem?id=2976
[POJ2728 Desert King]: http://poj.org/problem?id=2728
[P1768]: https://www.luogu.com.cn/problem/P1768
[Acwing361]: https://www.acwing.com/problem/content/363/
[Acwing2279]: https://www.acwing.com/problem/content/2281/
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/113454787