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]]。