前情提要

在上一讲动态规划初步里面,我们从暴力递归的局限性引出了动态规划,并且知道了动态规划其实是对穷举的优化。和递归不同,它一般是自底向上通过迭代的方法来解决问题的。DP的三要素是最优子结构(可以暴力递归的前提)重叠子问题(需要使用DP优化递归的前提)状态转移方程(DP需要进行的操作)

上一篇是DP的入门篇,解决了为什么要使用DP的问题。这一篇作为DP的基础篇,将以三大经典的背包问题为主线,进一步学习动态规划。


0-1背包问题

引入

前一篇中讲到了打家劫舍这个问题,如果将问题稍微改一下:

贼,夜入豪宅,可偷之物甚多,而负重能力有限。怎么偷才能更加不枉此行?

稍微分析一下,这个问题和之前的“打家劫舍”的区别就是多了一个负重能力作为限制因素。但是负重能力和打劫到第n间这个状态参数之间并没有明显的联系,我们该怎么做呢?

前信奥大佬(划去) 某lsp的回答……请无视

其实,这个问题的模型就是0-1背包。其问题描述如下:

N 个物品和一个容量(可装重量)为M 的背包,第i(0<=i<=N-1) 件物品的开销(重量)是cost[i] ,第i件物品的价值是value[i] 。问将哪些物品放入背包可使总价值最大。

(cost和value下面用c、v简写。)

0-1背包问题经典得简直就是动态规划的Hello,World! 。所以下面直接用背包问题来讲解。


0-1背包思路分析

首先为什么叫做0-1背包 呢?因为对于每个待选物品,我们只有选和不选两个选项。那到底该选还是不该选呢?这就需要用到题目中的限制因素:背包容量。

对于一个物品,如果我们选了它,那么剩余的背包容量就会发生变化。所以我们考虑将背包的容量 也作为一个状态参量,它和另外一个状态参量:选到第i个物品 共同标识一个状态。

现在标识一个状态用到了两个状态参量,所以我们可以画二维表来直观地表示每一个状态。考虑初始化状态:当背包容量为0时,装的物品价值为0;当没有物品可以选时,背包再大能选的物品价值也只有0。据此画出初始表如下:

接下来的关键是思考状态转移方程,即怎么依据前面的状态更新下一个状态

因为一个物品只有选和不选两个选项,如果不选的话 ,那么这个状态的值就和上一行相同背包容量位置的值一样;如果选了的话 ,那么就需要在上一行目前剩余背包容量位置的值的基础上加上这个物品的价值。两者取最大值就是这个状态的最优解。

故状态转移方程如下:(先不考虑边界状态)

$DP[i][j]=max(DP[i-1][j],DP[i-1][j-c[i]]+v[i]),0<=i<N,0<j<=M$

解决了状态转移方程,0-1背包也算是解决80%了。


通过之前的分析,可以发现,确定一个状态,我们只需要知道上一行。所以可以把二维表优化为一维表,以减小空间复杂度。故状态转移方程如下:

$DP[j]=max(DP[j],DP[j-c[i]]+v[i]),0<=i<N,0<j<=M$

但是存在的一个问题是决策时需要用到“上一行”较前位置状态的值,但是如果从左往右更新状态的话,一维表中那个状态可能会被新的状态覆盖——即所谓的状态污染 。所以我们从右往左更新状态值。

代码

0-1背包的原题可以在lintcode上找到->传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int backPackII(int m, vector<int> &A, vector<int> &V) {
int amount=A.size();
//一维DP数组,初始化为全0作为二维DP中的第一行
vector<int> DP(m+1,0);
//从上往下更新
for(int i=0;i<amount;i++)
//从右往左更新
for(int j=m;j>=0;j--)
//只有背包足以装下这个物品时才判断,否则不变
if(j>=A[i]) DP[j]=max(DP[j],DP[j-A[i]]+V[i]);
return DP[m];
}
};

分析一下复杂度,可以发现,时间复杂度为$O(MN)$,空间复杂度为$O(M)$(不考虑已经给出的空间)。

当然,既然从右往左,那么最后一行完全没有必要算完:(这样又可以杀掉一波人了)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int backPackII(int m, vector<int> &A, vector<int> &V) {
int amount=A.size();
vector<int> DP(m+1,0);
for(int i=0;i<amount;i++)
for(int j=m;j>=0;j--){
if(j>=A[i]) DP[j]=max(DP[j],DP[j-A[i]]+V[i]);
if(i==amount-1) break;
}
return DP[m];
}
};

最后一块石头的重量 II

力扣上也有0-1背包的题,但是0-1背包模型隐藏地相当深,很不容易发现->传送门

题目

有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0。

示例 1:输入:stones = [2,7,4,1,8,1] 输出:1

解释:
组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1],
组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1],
组合 2 和 1,得到 1,所以数组转化为 [1,1,1],
组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。

这道题的背包模型真的隐藏地很深!所以我们先来分析一下这道题。

我们把示例的过程用下面一个式子来表示:

$1=1-((8-7)-((4-2)-1)$

再化简一下就是:

$1=1+7+4-8-2-1$

如果还没看出来,那么再化一下:

$1=(1+7+4)-(8+2+1)$

现在应该很明显了,要使最后的结果最小,就要使两边的和相差最小。转化为0-1背包模型:背包容量为所有数和的一半,物品的价值就是石头的重量,每个物品的开销也是对应石头的重量。

需要注意的是和为奇数和偶数两种情况,这时我们应该选择是该向下取整还是向上取整。因为我们开始并不知道最后大数(等式左边)和小数(等式右边)的差值,所以DP得到的结果应该是小数,那么为了统一,应该选择向下取整

接下来的处理就同0-1背包差不多了。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum=0;
for(auto i:stones) sum+=i;
int capability=sum/2;
vector<int> DP(capability+1,0);
for(int j=0;j<stones.size();j++)
for(int i=capability;i>=0;i--)
if(i>=stones[j])
DP[i]=max(DP[i],DP[i-stones[j]]+stones[j]);
return sum-2*DP[capability];
}
};

完全背包问题

完全背包的原题可以在lintcode上找到->传送门

有N种物品和一个容量为M的背包,每种物品都无限可用。放入第i种物品的费用是c[i]价值是w[i] 。问怎么装才能使背包所装的物品价值最大?

普通做法

先思考一下,0-1背包的”0和1”代表选和不选,那么完全背包的”完全”代表什么呢?

和0-1背包对比一下就知道,完全背包对每件物品的选择不是选和不选,而是选0件、1件、……$\frac{M}{c[i]}$件。相应地,我们需要在状态转移方程上做出改变:

$DP[j]=max(DP[j],DP[j-k\times c[i]]+k\times v[i]),0<=i<N,0<j<=M,0<k<=\frac{M}{c[i]}$

这样做时我们同样需要从右往左更新状态避免状态污染。因为还要判断物品的选几个最好,所以我们在原来的两重循环的基础上,还要加一个循环来遍历物品可选的次数。故代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int backPackIII(vector<int> &C, vector<int> &V, int m) {
int amount=C.size();
vector<int> DP(m+1,0);
for(int i=0;i<amount;i++)
for(int j=m;j>=0;j--)
for(int k=0;k<=j/C[i];k++)
DP[j]=max(DP[j],DP[j-k*C[i]]+k*V[i]);
return DP[m];
}
};

时间复杂度为$O(MN\times \sum_{i=0}^N \frac{M}{c[i]})$,相比0-1背包的$O(MN)$可以说是多了一个数量级。该说真不愧是完全背包啊!

转化为0-1背包

要将完全背包转化为0-1背包的思路也很容易想到。我们只需要将一个物品的倍数作为另一个待选物品即可,最终待选的物品总数量为$N \times \sum_{i=0}^N \frac{M}{c[i]}$。

根据0-1背包的时间复杂度,可以推出这种做法的时间复杂度同样为$O(MN\times \sum_{i=0}^N \frac{M}{c[i]})$。

将完全背包问题转化为0-1背包后时间复杂度并没有减少,空间复杂度反而增加了很多。所以这个转化只能为我们解完全背包提供一个思路,并没有多大的实用价值。

下面继续探讨如何对完全背包进行优化。

时间优化

普通的做法是每次决策时都遍历物品可选个数,从中选出使该状态价值最大的物品个数。为了避免状态污染,所以需要从右往左更新状态。但是如果我们从左往右更新状态会怎样呢?

如果从左往右更新的话,更新的状态会依赖之前所选的该物品的个数。由于完全背包的特点是物品个数不限,所以这正是我们所需要的——将所选物品个数随着状态的更新一起更新

现在状态转移方程就是这样的:

$DP[j]=max(DP[j],DP[j-c[i]]+v[i]),0<=i<N,0<j<=M$

看起来和0-1背包的状态转移方程差不多。唯一的区别就是j从0加到M ,而不是从M减到0。

据此写出代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int backPackIII(vector<int> &cost, vector<int> &value, int m) {
int amount=cost.size();
vector<int> DP(m+1,0);
for(int i=0;i<amount;i++)
for(int j=0;j<=m;j++)
if(j>=cost[i])
DP[j]=max(DP[j],DP[j-cost[i]]+value[i]);
return DP[m];
}
};

时间复杂度为$O(MN)$,这样的优化已经很成功了!

读者不妨将上面的代码到lintcode提交一下对比优化前后的运行时间。

零钱兑换

力扣上也有完全背包的类似题目->传送门

题目

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1

你可以认为每种硬币的数量是无限的。

示例 1:输入:coins = [1, 2, 5], amount = 11 输出:3
解释:11 = 5 + 5 + 1

这道题和完全背包的区别就是它让我们求的不是最大值,而是最小值:需要凑的金额就是背包容量,硬币的面额就是放一个物品的代价,每个物品的价值都是1,最后求背包能放物品的最小价值。

状态转移方程如下:

$DP[j]=min(DP[j],DP[j-coins[i]]+1),0<=i<N,0<j<=amount$

为了取最小的值,初始话时应该将DP数组赋值为很大的数。

需要注意的一点是,要想到所有硬币不能凑出这个金额的情况应该如何处理:如果所有硬币都凑不出这个金额,那么对于每个i,同样凑不出这个金额。那么DP[amount]就不会更新,一直保持初始化时的那个很大的数。所以最后只需要判断一下是否改变即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int len=coins.size();
vector<int> DP(amount+1,amount+1);
DP[0]=0;
for(int i=0;i<len;i++)
for(int j=0;j<=amount;j++)
if(j>=coins[i])
DP[j]=min(DP[j],DP[j-coins[i]]+1);
return (DP[amount]==amount+1)?-1:DP[amount];
}
};

注意这个“很大的数”是相对的,amount+1刚好。

多重背包

lintcode上的多重背包问题->传送门

多重背包是三大基础背包问题的最后一个,它的问题描述如下:

有N种物品和一个容量为M的背包,第i件物品最多有A[i]件可用。放入第i种物品的费用是c[i]价值是v[i] 。问怎么装才能使背包所装的物品价值最大?

普通做法

和完全背包不同,它对物品的数量进行了限制。对于普通做法,我们只需要改一下遍历的物品个数即可,状态转移方程如下:

$DP[j]=max(DP[j-k\times c[i]]+v[i] \quad|\quad 0<=k<=A[i])$

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int backPackVII(int n,vector<int> &costs,vector<int> &value,vector<int> &amounts){
vector<int> DP(n+1,0);
int len=costs.size();
for(int i=0;i<len;i++)
for(int j=n;j>=0;j--){
for(int k=1;k<=amounts[i];k++)
if(j>=k*costs[i]){
DP[j]=max(DP[j],DP[j-k*costs[i]]+k*value[i]);
}
}
return DP[n];
}
};

这个做法的缺点同样是效率太低,所以我们接下来思考优化的方法。

二进制优化

先将多重背包转化为0-1背包,那么待选的物品数变成了$N\times \sum_{i=0}^NA[i]$,同样不能降低时间复杂度。但是,考虑到数论中有这样一个定理:

使用二进制可以表示任何一个数。

比如:50可以拆分为$2^0+2^1+2^2+2^3+2^4+(50+1-2^5)=1+2+4+8+16+19$

使用这6个数,可以表示小于等于50的任何数——这也很容易证明,所以证明略去。

这样,我们不需要添加50个新的待选物品,而只需要将这6个物品作为待选,通过选或不选,即0和1,就可以表示出50以内的任意组合

由于使用了二进制,所以待选物品总数变成了$N\times \sum_{i=0}^NlogA[i]$,在很大程度上优化了时间复杂度。

代码&注释如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int backPackVII(int n, vector<int> &costs, vector<int> &value, vector<int> &amounts) {
//使用二进制组合
int len=costs.size();
for(int i=0,j;i<len;i++){
for(j=1;pow(2,j+1)<amounts[i];j++){
costs.emplace_back(costs[i]*pow(2,j));
value.emplace_back(value[i]*pow(2,j));
}
int temp=amounts[i]-pow(2,j)+1;
costs.emplace_back(costs[i]*temp);
value.emplace_back(value[i]*temp);
}
//0-1背包求解
len=costs.size();
vector<int> DP(n+1,0);
for(int i=0;i<len;i++)
for(int j=n;j>=0;j--)
if(j>=costs[i]){
DP[j]=max(DP[j],DP[j-costs[i]]+value[i]);
if(i==len-1) break;
}
return DP[n];
}
};

多重背包另外还有一种O(MN)的优化——单调队列优化,因为需要证明的比较多,所以这里就不写了,还请读者接下来自行研究。(我尽可能也把思路整理出来)指还不会……->传送门