长江后浪推前浪，前浪死在沙滩上。这句诗句用来形容动态规划再好不过。的确，动态规划是解决一些棘手的问题的好办法。动态规划的主要思路就是把大问题分解为小问题。动态规划大致分为四种，线性动规、区域动规、树形动规、背包动规。其中，背包动归分为01背包、完全背包和分组背包。这篇文章介绍的是动态规划中背包动归的01背包。让我们通过吃货明明的背包一起了解一下01背包
题目大意
题意
明明是一个吃货。今天他来到了一家快餐店，这家快餐店里有样美食，每一样美食都有一个美味度
和重量
。现在明明背着一个背包，他想打包带走一些美食，但背包的重量有限，重量为
。请问明明可以获得的最大美味度为多少？
输入格式
输入共3行，第一行为美食的数量和背包的重量
，第二行有
个数据，第
个数据代表美味度
，第三行
个数据，第
个数据代表重量
。
输出格式
一个数，表示明明可以获得的最大美味度。
输入样例
3 4
3000 2000 1500
4 3 1
输出样例
3500
简单枚举
简单枚举思路大致如下：尝试各种美食的配列组合。这很显然是暴力的枚举，但这很慢。让我们利用样例观察一下简单枚举的过程。
| 第1种美食 | 第2种美食 | 第3种美食 |
|---|---|---|
| 3000 | 2000 | 1500 |
| 4 | 3 | 1 |
上图中，第一行是为每一种美食标的编号，第二行是每一种美食的美味度，第三行是每一种美食的重量。
枚举的过程如下：
| 选择的美食 | 美味度 | 是否装的下 |
|---|---|---|
| 不选 | 0 | 当然装得下 |
| 1 | 3000 | Y |
| 2 | 2000 | Y |
| 3 | 1500 | Y |
| 1+2 | 5000 | N |
| 1+3 | 4500 | N |
| 2+3 | 3500 | Y |
| 1+2+3 | 6500 | N |
可见这种算法要把的子集算出来。这样当然效率低下，因为我们知道
的子集数量为
。很显然，时间复杂度就是
。若
,就要枚举
。这并不奇怪，因为指数阶的时间复杂度仅次于阶乘阶！
动态规划思路
前面我们讲过，动态规划的原理就是把大问题分成小问题。换句话来说，就是，利用算过的东西来推出将要算的东西。
我们以斐波那契数列为例：
| f | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
f数组是斐波那契数列的数组。现在，假如我想要求第七项，也就是f[7]，那么我们应该怎样算呢？
最容易想到的是一个递归，就像这样：
int f(int now){
if(now == 1 || now == 2)return 1;
return f(now - 1) + f(now - 2);
}
但是这样导致了一个问题：当我计算f[7]的时候，我又计算了f[6]和f[5]，计算f[6]是我要计算f[5]和f[4]，紧接着计算f[4]，我又需要计算f[3]以及f[2]。这时我们发现，我们进行了重复计算！
标注①意思为return1。从这张图可见，递归做法的时间复杂度是树形的
那么，如何解决重复计算？
我们可以使用一个数组f来记录之前遍历过的部分。代码如下：
int f[20];
f[1]=1;
f[2]=1;
for(int i=3;i<=7;i++){
f[i]=f[i-1]+f[i-2];
}
这样的算法变成线性算法。
动态规划做法
列出状态转移方程
有了思路，现在讨论如何解决这个问题。
首先，上文中被我们称为状态转移方程。这一个关系式表示了如何利用之前出现过的量推出现在的量。解出动态规划问题，最关键的步骤就是写出状态转移方程。
让我们重新审视一下题目：
明明是一个吃货。今天他来到了一家快餐店，这家快餐店里有
样美食，每一样美食都有一个美味度
和重量
。现在明明背着一个背包，他想打包带走一些美食，但背包的重量有限，重量为
。请问明明可以获得的最大美味度为多少？
这时，我们发现：题目中出现了两个量，美味度和重量。这时我们不能单纯用，而要用
。
表示在第
个重量里，选择前
个美食，能够使明明的满意度最高。
接着，我们要列出状态转移方程。我们可以利用一下样例。
| 第1种美食 | 第2种美食 | 第3种美食 |
|---|---|---|
| 3000 | 2000 | 1500 |
| 4 | 3 | 1 |
让我们根据刚才对表的定义，画出
这张表（你可以先自己试试看）：
我们发现，对于每一种美食，仅仅有两种方案。
- 选
- 不选
如果不选第件美食，那么
的最大满意值会是多少呢？
让我们思考一下，如果不选的话，背包的重量不变，只是不装第
件美食。不装第
件美食，那么状态就应该跟上一件美食的状态相等。
也就是说，在不选第件美食的时候，
如果选第件美食，那么
的最大满意值会是多少呢？
我们发现，如果选的话，那么就应该等于某个状态加上美味度
，也就是说，
那么问号怎么计算呢？这就有一些烧脑子。这里用递推法：装了第件美食，背包里就增重了重量
。因此在选这件美食之前，背包重量为
（j是现在背包重量）。因此问号部分就是
因此选择第件美食的状态转移方程就是
因为我们要求最大值，因此完整的状态转移方程是：
讨论边界
上述的状态转移方程其实有一些问题。如果背包装不下第件美食，那么我们就不能选择。最好的方法就是判断
。如果小于0，那么就装不下。
示例代码
#include <iostream>
using namespace std;
int n,p;
int e[1005],w[1005];
int f[1005][1005];
int main(){
cin >> n >> p;
for(int i=1;i<=n;i++){
cin >> e[i];
}
for(int i=1;i<=n;i++){
cin >> w[i];
}
for(int i=1;i<=n;i++){//选择前i个美食
for(int j=1;j<=p;j++){//在第j重量
if(j-w[i]>=0 && f[i-1][j-w[i]]+e[i]>f[i-1][j])//边界判断+判断选/不选
f[i][j]=f[i-1][j-w[i]]+e[i];//选
else
f[i][j]=f[i-1][j];//不选
}
}
cout << f[n][p];
return 0;
}
动归优化
我们可以看见，我们把时间复杂度从降到
。当然，空间复杂度也为
。然而空间复杂度是可以下降的。让我们再次通过斐波那契数列看一下
斐波那契数列降空间复杂度
这种方法被我们称作“滚动”。第一次，我们这样实现斐波那契数列：
int f[20];
f[1]=1;
f[2]=1;
for(int i=3;i<=7;i++){
f[i]=f[i-1]+f[i-2];
}
然而，要算到第七项，不需要开20的数组。其实我们发现，数列最关心的是和
。也就是说，三个数组就能够满足要求：
int a,b,c;//a记录f[i-2],b记录f[i-1],c记录f[i]
a=1,b=1;
for(int i=3;i<=7;i++){
c=a+b;
a=b;
b=c;
}
由于空间复杂度忽略常数，我们可以认为，上述代码空间复杂度从降至
。
由此我们便学会了完整的01背包问题。因为最后的优化过于简单，不给予示例代码了。
网友评论