|
|
## $01$分数规划
|
|
|
|
|
|
【挖坑待填】
|
|
|
|
|
|
> 水平所限，01分数规划刚刚入门，还是由SPFA求负环的题引入的01分数规划，还是完成了入门篇之后，回到学习主线，继续学习SPFA+负环的图论章节，待知识体系完善后，三刷再来攻克其它相关试题。
|
|
|
> 黄海 于2022-11-10 17:04
|
|
|
|
|
|
|
|
|
[01分数规划问题 - 笔记](https://blog.csdn.net/qq_43803508/article/details/107115444)
|
|
|
|
|
|
[牛人精讲](https://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html)
|
|
|
|
|
|
[OI Wiki](https://oi-wiki.org/tools/)
|
|
|
|
|
|
[专题 01分数规划保证你看不懂](https://blog.csdn.net/weixin_44577381/article/details/100024025)
|
|
|
|
|
|
### 一、定义
|
|
|
$01$分数规划问题：所谓的$01$分数规划问题就是指这样的一类问题，给定两个数组，$a[i]$表示选取$i$的收益，$b[i]$表示选取$i$的代价。如果选取$i$，定义$w[i]=1$否则$w[i]=0$。每一个物品只有选或者不选两种方案，求一个选择方案使得
|
|
|
$$\large \displaystyle R=\frac{\sum (a[i] \times w[i])}{\sum (b[i]\times w[i])}$$
|
|
|
|
|
|
取得最值，即所有选择物品的总收益/总代价的值 **最大** 或是 **最小**
|
|
|
|
|
|
$01$分数规划问题主要包含一般的$01$分数规划、最优比率生成树问题、最优比率环问题、最大密度子图等。我们将会对这四个问题进行讨论。
|
|
|
<font color='red' size=4><b>
|
|
|
永远要记得，我们的目标是使$R$取到最值。这句话我会在文中反复的强调
|
|
|
</b></font>
|
|
|
|
|
|
### 二、为啥不能直接按性价比排序，从大到小找出指定个数不就行了吗？
|
|
|
如果真要这么干，那是贪心的作法，这样做是不对的，原因：
|
|
|
举个反例：
|
|
|
|
|
|
$$\LARGE \frac{3}{1} ~~~~ \frac{80}{40}(\frac{2\times 40}{1\times 40}) ~~~~ \frac{1.9}{1}$$
|
|
|
|
|
|
$k=2$,就是需要选择出两组来，保证选择的性价比值最高。
|
|
|
|
|
|
形象化理解一下：
|
|
|
* ① $\large \displaystyle \frac{3}{1}$,表示价值$3$,重量$1$
|
|
|
* ② $\large \displaystyle \frac{80}{40}$,表示价值$80$,重量$40$
|
|
|
* ③ $\large \displaystyle \frac{1.9}{1}$,表示价值$1.9$,重量$1$
|
|
|
|
|
|
按单个性价比排序，应该是 $\large ①>②>③$，按贪心思想，应该选择$\large ①,②$
|
|
|
|
|
|
而如果按上面加和，除以，下面加和的话就是：
|
|
|
|
|
|
$\displaystyle①+②=\frac{3+80}{1+40}=2.024$
|
|
|
|
|
|
$\displaystyle ①+③=\frac{3+1.9}{1+1}=2.45$
|
|
|
很明显$\large ①+③>①+②$
|
|
|
|
|
|
应该选择 $\large ①+③$这个组合!
|
|
|
|
|
|
<font color='red' size=4><b>总结：上来就除，除完再排名，和，上面加和 除以 下面加和 不是一回事，要想清楚！</b></font>
|
|
|
|
|
|
### 三、分析过程
|
|
|
数学分析中一个 **很重要的方法** 就是 **分析目标式**，来看目标式:
|
|
|
|
|
|
$$\large \displaystyle R =\frac{\sum (a[i]\times w[i])}{\sum(b[i]\times w[i])}$$
|
|
|
|
|
|
分析一下它有什么性质:
|
|
|
|
|
|
我们先定义一个函数
|
|
|
$$\large F(L):=\sum(a[i]\times w[i])-L\times \sum(b[i]\times w[i])$$
|
|
|
|
|
|
显然这只是对目标式的一个简单的变形。
|
|
|
|
|
|
**分离参数**，得到
|
|
|
$$\large F(L):= w[i] \times \sum(a[i]-L\times b[i])$$
|
|
|
|
|
|
|
|
|
这时我们就会发现，**如果$L$已知的话**，$\large a[i]-L\times b[i]$就是已知的，<font color='blue' size=4><b>当然$w[i]$是未知的</b></font> 。记
|
|
|
$$\large d[i]=a[i]-L\times b[i]$$
|
|
|
那么
|
|
|
$$\large F(L):=w[i]\times \sum(d[i]*x[i])$$
|
|
|
多么简洁的式子,我们就对这些东西下手了。
|
|
|
|
|
|
<font color='red' size=4><b>再次提醒一下，我们的目标是使$R$取到最大值</b></font>
|
|
|
|
|
|
我们来分析一下这个函数，它与目标式的关系非常的密切，$L$就是目标式中的$R$，最大化$R$也就是最大化$L$。
|
|
|
|
|
|
$F$的值是由两个变量共同决定的，即方案$X$和参数$L$。<font color='blue' size=4><b>对于一个确定的参数$L$来说，方案的不同会导致对应的$F$值的不同</b></font>，那么这些东西对我们有什么用呢?
|
|
|
|
|
|
假设我们已知存在一个方案$X$使得$F(L)>0$，这能够证明什么?
|
|
|
$$\large F(L):=\sum (a[i]\times w[i])-L\times \sum (b[i]\times w[i])>0$$
|
|
|
即
|
|
|
$$\large \frac{\sum(a[i]\times w[i])}{\sum(b[i]\times w[i])} >L$$
|
|
|
|
|
|
也就是说，如果一个方案使得$F(L)>0$说明了这组方案可以得到一个比现在的$L$更优的一个$L'$，既然有一个更优的解，那么为什么不用呢？
|
|
|
|
|
|
显然，$d$数组是随着$L$的增大而单调减的。也就是说，存在一个临界的$L$使得不存在一种方案，能够使$F(L)>0$. 我们猜想，这个时候的$L$就是我们要求的 **最优解**。之后更大的$L$值则会造成无论任何一种方案，都会使$F(L)<0$.类似于上面的那个变形，我们知道，$F(L)<0$是没有意义的，因为这时候的$L$是不能够被取得的。当$F(L)=0$使，对应方案的$R$值恰好等于此时的$L$值。
|
|
|
|
|
|
综上，函数$F(L)$有这样的一个性质：在前一段$L$中可以找到一组对应的$X$使得$F(L)>0$，这就提供了一种证据，即有一个比现在的$L$更优的解，而在某个$L$值，存在一组解使得$F(L)=0$,且其他的$F(L)<0$，这时的$L$无法继续增大，即这个$L$就是我们期望的最优解，之后的$L$会使得无论哪种方案都会造成$F(L)<0$.而我们已经知道，$F(L)<0$是没有任何意义的，因为此时的$L$值根本取不到。
|
|
|
|
|
|
<font color='red' size=4><b>最后一次提醒，我们的目标是$R$！！！</b></font>
|
|
|
|
|
|
如果现在你觉得有些晕的话，那么我要提醒你的就是，千万不要把$F$值同$R$值混淆。$F$值是根据我们的变形式求的$d$数组来计算的，而$R$值则是我们所需要的真实值，他的计算是有目标式决定的。$F$值只是提供了一个证据，告诉我们真正最优的$R$值在哪里，他与$R$值本身并没有什么必然的联系。
|
|
|
|
|
|
根据这样的一段性质，很自然的就可以想到二分$L$值，然后验证是否存在一组解使得$F(L)>0$，有就移动下界，没有就移动上界。
|
|
|
|
|
|
所有的$01$分数规划都可以这么做，唯一的区别就在于求解时的不同——因为每一道题的限制条件不同，并不是每一个解都是可行解的。比如在普通的数组中，你可以选取$1、2、3$号元素，但在生成树问题中，假设$1、2、3$号元素恰好构成了一个环，那就不能够同时选择了，这就是需要具体问题，具体分析的部分。
|
|
|
|
|
|
二分是一个非常通用的办法，但是我们来考虑这样的一个问题，二分的时候我们只是用到了$F(L)>0$这个条件，而对于使得$F(L)>0$的这组解所求到的$R$值没有使用。因为$F(L)>0$,我们已经知道了$R$是一个更优的解，与其漫无目的的二分，为什么不将解移动到$R$上去呢？求$01$分数规划的另一个方法就是$Dinkelbach$算法，他就是基于这样的一个思想，他并不会去二分答案，而是先随便给定一个答案，然后根据更优的解不断移动答案，逼近最优解。由于他对每次判定使用的更加充分，所以它比二分会快上很多。但是，他的弊端就是需要保存这个解，而我们知道，有时候验证一个解和求得一个解的复杂度是不同的。二分和$Dinkelbach$算法写法都非常简单，各有长处，大家要根据题目谨慎使用。
|
|
|
|
|
|
### 五、实践
|
|
|
上面啰嗦了这么多，现在给出程序的框架。
|
|
|
|
|
|
#### 二分法
|
|
|
```c++
|
|
|
L = 1 ; R = INF;
|
|
|
while( R - L > Eps)
|
|
|
Mid:=(L+R)/2;
|
|
|
For I=1..X do D[i]:=A[i]-Mid*B[i];//根据Mid计算D数组
|
|
|
if check(Mid)
|
|
|
L:=Mid;
|
|
|
else
|
|
|
R:=Mid；
|
|
|
```
|
|
|
#### $Dinkelbach$算法
|
|
|
```c++
|
|
|
L:=随便什么东西;
|
|
|
Repeat
|
|
|
Ans:=L;
|
|
|
For I=1..X do D[i]:=A[i]-L*B[i];//根据L计算D数组
|
|
|
检查解并记录;
|
|
|
p:=0;q:=0;
|
|
|
for I=每一个元素 do
|
|
|
如果元素I在解中
|
|
|
begin
|
|
|
p:=p+A[i];q:=q+B[i];
|
|
|
end;
|
|
|
L:=p/q;//更新解
|
|
|
Until abs(Ans-L)<Eps;
|
|
|
```
|
|
|
其中检查解的部分是要看具体情况的。
|
|
|
|
|
|
|
|
|
|
|
|
### 三、常见模型
|
|
|
|
|
|
#### 1、$01$规划
|
|
|
裸$01$规划
|
|
|
例题：[POJ2976 Dropping tests](http://poj.org/problem?id=2976)
|
|
|
|
|
|
大意：给定$A$数组$B$数组，让求删除$k$个数后,即保留(选择) $N-K$个使得$R$最大，输出$Round(100*R)$
|
|
|
|
|
|
分析：限制很简单，只是数目上有所限制，处理方法也很简单，求出$D$数组后从大到小排列，从前向后取$N-K$个即可，这时的$D$一定是最大的。
|
|
|
|
|
|
|
|
|
另外：如果是最小选择$N-K$个怎么办？
|
|
|
|
|
|
办法是一样的，从大到小排列序，傻子才多选，能少选就少选。反正$F$值具体的大小没什么关系，我们只要知道他与$0$的关系即可。
|
|
|
|
|
|
```c++
|
|
|
#include <cstdio>
|
|
|
#include <iostream>
|
|
|
#include <algorithm>
|
|
|
#include <cmath>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 1010;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
int n, k;
|
|
|
int a[N], b[N];
|
|
|
const double eps = 1e-8;
|
|
|
|
|
|
double d[N];
|
|
|
|
|
|
bool check(double x) {
|
|
|
for (int i = 0; i < n; i++) d[i] = a[i] - x * b[i];
|
|
|
sort(d, d + n, greater<double>()); //由大到小排序
|
|
|
|
|
|
double sum = 0;
|
|
|
for (int i = 0; i < n - k; i++) sum += d[i];
|
|
|
return sum >= 0; //从大到小选n-k个，看ans是否为可行的解
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
while (cin >> n >> k && (n || k)) {
|
|
|
for (int i = 0; i < n; i++) cin >> a[i];
|
|
|
for (int i = 0; i < n; i++) cin >> b[i];
|
|
|
|
|
|
//浮点数二分
|
|
|
double l = 0, r = INF;
|
|
|
while (r - l > eps) {
|
|
|
double mid = (l + r) / 2; //注意浮点数不能用右移操作
|
|
|
if (check(mid))
|
|
|
l = mid; //向右逼近，使结果更大一些
|
|
|
else
|
|
|
r = mid; //向左逼近，使结果更小一些
|
|
|
}
|
|
|
printf("%.0lf\n", l * 100); // 四舍五入
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
#### 2、$01$规划与最小生成树
|
|
|
最优比率生成树
|
|
|
例题：[POJ2728 Desert King](http://poj.org/problem?id=2728)
|
|
|
|
|
|
#### 3、01规划与环
|
|
|
最优比率生成环
|
|
|
例题：[$P1768$ 天路](https://www.luogu.com.cn/problem/P1768)
|
|
|
[$Acwing$ $361$ 观光奶牛](https://www.acwing.com/problem/content/363/)
|
|
|
|
|
|
#### 4、$01$规划与网络流
|
|
|
**最优比率最小割**
|
|
|
例题：[$Acwing$ $2279$ 网络战争](https://www.acwing.com/problem/content/2281/)
|
|
|
题解：[网络战争](https://blog.csdn.net/qq_45735851/article/details/113454787)
|
|
|
|
|
|
[POJ2728]Desert King
|
|
|
[POJ3621]Sightseeing Cows
|
|
|
|
