1. 01背包

01背包问题是经典的 多阶段动态规划 问题。

多阶段动态规划问题:可以描述成若干个有序阶段,且每个阶段的状态只和上一个阶段的状态有关。

如图所示,阶段2的D状态是由阶段1的AB状态决定的,C状态是由A状态决定的。

01背包也是如此,前i个物品装入背包的最大价值是由前i-1个物品装入背包的最大价值决定的。

问题描述

n件物品,每件物品的体积为w[i],价值为v[i],每件物品的体积都不相同,现有一个容量为W的背包,问怎么装才能使得背包内的价值最大?

思路

用暴力法可解,但是时间复杂度为O(2n)O(2^n),这是不能接受的。而用动态规划算法可以将其降到O(nV)O(nV)

dp[i][j]表示前i件物品装入容量为j的背包中所能获得的最大价值。

比如说,3件物品w=[1,2,3], v=[2,3,7],则前3件物品装入容量为3的背包中所获得的最大价值为7。

考虑对dp[i][j]的求解:

  1. 如果w[i]>j,即背包放不下第i件物品,显然有dp[i][j] = dp[i-1][j]
  2. 如果w[i]<=j,则此时有两种选择,放还是不放。
    • 放的话,则dp[i][j] = dp[i-1][j-w[i]] +v[i]
    • 不放的话,则dp[i][j] = dp[i-1][j]
    • dp[i][j] = max(dp[i-1][j-w[i]] +v[i], dp[i-1][j])

犹记得上次学背包问题还是大二,现在都研一了,过了太久了,已经忘没了。所以当我再看到这个式子时,有些纳闷,为啥会有两种选择放还是不放,既然背包容量够大,那肯定放啊,还用问吗?

其实这种想法是不对的,这是贪心的思路,贪心就是当前状态依赖于前一个状态

而01背包不是这样的,它的当前状态依赖于前一行状态,至少从式子中我们可以看出,它依赖于dp[i-1][j-w[i]]dp[i-1][j]这两个状态。

前一行状态的就是dp[i-1][1], dp[i-1][2], …, dp[i-1][W]

究其原因,这种错误想法的来源就是忽略了空间,dp数组是一个二维空间,放了,就说明当前状态是从dp[i-1][j-w[i]]变化过来的,不放,就说明当前状态是从状态dp[i-1][j]变化过来的。

关于这个问题,可以参考知乎回答——能否讲讲你对01背包的理解

代码

由此,我们便可以写出01背包的核心代码:

1
2
3
4
5
6
7
8
for(int i=1; i<=n; i++) {  // 第1件物品到第n件物品
for(int j=1; j<=W; j++) { // 背包容量从1到W
if(w[i] < j) // 如果第i件物品体积大于背包容量
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
}
}

手推一遍dp数组的话会更加明白原理。

例子:01背包问题例子

滚动数组优化

从图中我们可以看到,第i行的状态只依赖于第i-1行,仅凭这点,我们就可以将二维数组优化为一维数组。

我们通过图和前面代码可以看到,dp[i][j]只依赖于它头上那个和它左上方的某个状态。所以如果我们要将其压缩为一维数组的话,就必须从右向左遍历更新了。

也就是说,我们创建一个一维数组,然后从右向左一遍遍的更新覆盖,覆盖一次,就对应二维数组中我们完成了一行的状态更新。

核心代码为:

1
2
3
4
5
6
7
8
9
for(int i=1; i<=n; i++) {
for(int j=W; j>=1; j--) {
if(w[i] < j)
// 右边的dp[j]表示原来的值,左边的表示更新后的值,在二维数组中dp[i][j]=dp[i-1][j],所以在一维数组中,该行代码可以去掉。
dp[j] = dp[j];
else
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}

例子

样例:

1
2
3
5   8   // n=5, W = 8
3 5 1 2 2 // w[i]
4 5 2 1 3 // v[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
#include <iostream>
#include<bits/stdc++.h>

using namespace std;

int n = 5, V = 8;
int dp[6][9];
int w[6] = {0,3,5,1,2,2};
int c[6] = {0,4,5,2,1,3};

int main()
{

for(int i=1; i<=n; i++) {
for(int j = w[i]; j<=8; j++) {
if(w[i] > j) dp[i][j] = dp[i-1][j];
else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);
}
}
for(int i = 0; i<=n; i++) {
for(int j = 0; j<=V; j++)
cout<<dp[i][j]<<" ";
cout<<endl;
}
}

dp数组为:

第0行和第0列都是0,分别表示前i个物品放入容量为0的背包中的最大价值和前0个物品放入容量为j的背包中的最大价值。

2. 完全背包

问题描述

完全背包较01背包的区别就是:完全背包每种体积的物品可以有无穷件。选一件物品时可以选一件,两件,…,只要不超过背包容量即可。

同样令dp[i][j]表示前i件物品放入容量为j的背包中的最大价值。

思路

和01背包也几乎是一样的。

  1. 如果w[i]>j,即背包放不下第i件物品,显然有dp[i][j] = dp[i-1][j]
  2. 如果w[i]<=j,则此时有两种选择,放还是不放。
    • 不放的话,则dp[i][j] = dp[i-1][j],这跟01背包是一样的;
    • 放的话,就不一样了,因为01背包每种物品只有一件,所以必须转移到dp[i-1][j-w[i]]这个状态,但是完全背包的话每种物品有无穷件,所以放了第i件物品后还可以放第i件物品,故转移到dp[i][j-w[i]]这个状态,所以dp[i][j] = dp[i][j-w[i]]+v[i]
    • dp[i][j] = max(dp[i][j-w[i]] +v[i], dp[i-1][j])

也就是说,完全背包和01背包的区别就是dp[i][j-w[i]]还是dp[i-1][j-w[i]]