0-1 背包

背包问题整体分为以下几种，情况比较复杂，但是对于面试的话，掌握01背包和完全背包，就差不多了，本篇主要介绍01背包和完全背包。 bag-issue

题干

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 bag 比如:

1
2
3

weight = [1, 3, 4]  // 三个物品
value = [15, 20, 30] // 对应该的价值
bagweight = 4 // 背包的容量为4

问背包能背的物品最大价值是多少？

解法一 二维数组

  1. 确定dp数组以及下标的含义

使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大dp[i][j]。

  1. 确定状态转移方程

在遍历到i 的时候，有两种情况来确定价值

  • 不放物品i；即背包容量为j，里面不放物品i的最大价值，此时dp[i][j] 就等于dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
  • 放物品i；dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值 由此可得: dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
  1. 数组初始化

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。 状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。 dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。 那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。 当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 第一列初始化为0
for (int j = 0 ; j < weight[0]; j++) {  
    // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略
    dp[0][j] = 0;
}
// 第一行初始化为value[0]
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
  1. 遍历顺序

由状态转移方程： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向（包括正上方向），那么先遍历物品，再遍历背包的过程 和 先遍历背包，再遍历物品 都可以让 (i-1,j) 和 (i-1, j-weight[i]) 先与(i,j) 所以这个遍历顺序都可以。但是建议还是先遍历物品，在遍历背包，符合大部分情况下的解法。

  1. 代码
 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// weightBag
func weightBag(weight, value []int, bagWeight int) int {
	// dp[i][j] 二维，第一维i 表示选择的物品，从weight 中找
	// 第二维 j 表示背包能放下的最大重量
	// dp[i][j] 表示从下标为[0-i]的物品里任意取(包含i)，放进容量为j的背包，价值总和最大是多少
	// dp[i][j] =
	// 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。
	// (其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
	// 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]]
	// 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

	n := len(weight)

	dp := make([][]int, n) // 第一维物品的个数
	for i := 0; i < n; i++ {
		dp[i] = make([]int, bagWeight+1) // 第二维，背包能放下的最大重量，包含bagWeight 本身
	}

	// 初始化dp
	// 当j为零的时候，价值最大为0
	for i := 0; i < n; i++ {
		dp[i][0] = 0
	}
	// 当i为零的时候，价值为value[0]
	// i 开始是weight[0] weight 是递增的
	for i := weight[0]; i < bagWeight+1; i++ {
		dp[0][i] = value[0]
	}

	// 为什么从1开始遍历，因为状态转移公式
	for i := 1; i < n; i++ { // 遍历物品
		for j := 0; j < bagWeight+1; j++ { // 遍历背包容量

			if j < weight[i] { // 物品不能放到背包中
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]]+value[i])
			}
		}
	}
	return dp[n-1][bagWeight]
}

解法二 一维数组

背包问题依赖分析

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) 有状态转移方程，看下图 依赖 从上图看我们在计算第i的数据的时候我们只依赖第i - 1行，我们在第i行从后往前遍历并不会破坏动态转移公式的要求。 我们已经很清楚了我们在计算dp数据的时候进行计算的时候只使用了两行数据，那么我们只需要申请两行的空间即可，不需要申请那么大的数组空间，计算的时候反复在两行数据当中交替计算既可。比如说我们已经计算好第一行的数据了（初始化），那么我们可以根据第一行得到的结果得到第二行，然后根据第二行，将计算的结结果重新存储到第一行，如此交替反复，像这种方法叫做滚动数组。

我们还能继续压缩空间吗🤣？我们在进行空间问题的优化的时候只要不破坏动态转移公式，只需要我们进行的优化能够满足dp[i][j]的计算在它所依赖的数据之后计算即可。

  • 根据动态转移公式dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])我们知道，第i行的第j个数据只依赖第i - 1行的前j个数据，跟第j个数据之后的数据没有关系。因此我们在使用一维数组的时候可以从后往前计算（且只能从后往前计算，如果从前往后计算会破坏动态转移公式，因为第j个数据跟他前面的数据有依赖关系，跟他后面的数据没有依赖关系）就能够满足我们的动态转移公式。 one-dim

  • 如果我们从在使用单行数组的时候从前往后计算，那么会使得一维数据前面部分数据的状态从i - 1行的状态变成第i行的状态，像下面这样 one-dim-2

  • 但是一维数组当中后部分的数据还是i - 1行的状态，当我们去更新他们的时候他们依赖前面部分数据的i - 1行的状态，但是他们已经更新到第i的状态了，因此破坏了动态规划的转移方程，但是如果我们从后往前进行遍历那么前面的状态始终是第i - 1行的状态，因此没有破坏动态规划的转移方程，因此我们需要从后往前遍历。 one-dim-3

一维数组具体分析

  1. 确定dp数组的定义

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是dp[i][j] 的值。 用一维数组之后dp[j]: 容量为j的背包，所背的物品价值可以最大为dp[j]

  1. 状态转移方程
  • 不放物品i: 一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]
  • 放物品i: dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]） 所以 dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
  1. 一维dp数组如何初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。 那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？ 看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。 这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

  1. 遍历顺序 结果如下
1
2
3
4
5
6
7

for i := 0; i < n; i++ { //遍历物品
    // 需要注意的是，j 一定要从大到小，防止物品0 被重复计算
    for j := bagWeight; j >= weight[i]; j-- { //遍历背包容量
        dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
    }

}

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

倒序遍历是为了保证物品i只被放入一次！ 但如果一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15 如果正序遍历 dp[1] = dp[1 - weight[0]] + value[0] = 15 dp[2] = dp[2 - weight[0]] + value[0] = 30 此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？ 倒序就是先算dp[2] dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0） dp[1] = dp[1 - weight[0]] + value[0] = 15

那么问题又来了，为什么二维dp数组遍历的时候不用倒序呢？ 因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！

再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？ 不可以！ 因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。

  1. 代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 背包优化
// dp + 滚动数组
func weightBag2(weight, value []int, bagWeight int) int {
	// dp[j] 表示 容量为j的背包，所背的物品价值可以最大为dp[j]
	// dp[j] = max(dp[j], dp[j-weight[i]] + val[i])
	// 此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，
	// 即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，

	dp := make([]int, bagWeight+1)

	// 初始化，背包容量为0，的时候价值都为0
	// dp 上面声明的时候，已经初始化

	n := len(weight)

	for i := 0; i < n; i++ { //遍历物品
		// 需要注意的是，j 一定要从大到小，防止物品0 被重复计算
		for j := bagWeight; j >= weight[i]; j-- { //遍历背包容量
			dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
		}

	}
	return dp[bagWeight]
}