害怕01背包问题的同学看过来，今天就把它讲清楚

写在前面

背包问题相信是很多同学害怕的问题，包括作者自己。本文将彻底把01背包问题讲透彻，争取下次遇到类似问题能轻松解决。

最近面试遇到一个算法题：给定一个数组，如nums=[1,2,3,4,6]，判断能不能将它分成2个子数组，2个子数组内元素之和相等。leetcode原题

作者第一反应是对数组求和1+2+3+4+6=16，然后除以2,得到8。这个算法题就转化成了从数组nums=[1,2,3,4,6]中选取部分数字，使得它们的和等于8。后面作者给出的方案是遍历每一个数字，用递归法。比如遍历到nums[i]的时候，判断数组剩下的元素能不能组合成8-nums[i]。这个思路时间复杂的很高。

有没有更好的思路呢？对01背包问题比较敏感的同学可能很快就想到了，转化后的问题不就是一个典型的01背包问题吗？对于每一个元素nums[i]要么取、要么不取，使得最终结果等于8。

下面来具体看看01背包问题。

01背包问题

背包问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

相似问题经常出现在商业、组合数学，计算复杂性理、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？

算法题描述

一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，求能够装入背包的最大价值是多少？

动态规划

说到背包，就一定要想到动态规划。

上面这条定律一定要记录，背包一定要用动态规划解决。当然也可以用暴力解决，但是时间复杂的很高，一般不推荐，也失去了01背包问题的讨论价值。

对于动态规划的思想，作者另外一篇文章最清晰易懂的动态规划详细讲解了一下，不清楚的可以先去看看。

核心思想就是分治法，大事化小小事化了。

对于01背包问题使用动态规划，难点就是递推公式。尤其是二维dp，很难想到。但是对于01背包的dp，我们可以记住它。能理解最好，不理解就记住。

二维dp数组

dp数组的含义

可能很多人会写动态规划的题目，会写01背包，但是很多人却不会去注重思考dp数组的含义，其代表着什么？

01背包的dp数组含义是：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

不懂可以看看下面图，仔细想想。

递推公式

dp[i][j]=Max( dp[i-1][j] , dp[i-1][ j-wᵢ ]+vᵢ )

dp[i][j]我们在上面知道 这 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。此时我们应该考虑下标为i物品是否放入背包（先要考虑j-wᵢ是否大于等于0，即此时是否能够放入物品i ），于是就有两种情况：放 或者 不放。

不放物品i就是dp[i-1][j]嘛，放物品i就是容量为j的背包需要留出这个物品i的容量才可以放物品i，即dp[i-1][ j-wᵢ ],而这又是下标为 0到 i-1 的物品里任意取，放进容量为 j-wᵢ 的背包，最大的价值总和。然后再由 dp[i-1][ j-wᵢ ]+vᵢ 就是dp[i][j]放物品 i 的最大价值。

然后 取 Max( dp[i-1][j] , dp[i-1][ j-wᵢ ]+vᵢ ) 二者的最大值。

dp数组的初始化

我们由上面知道了求 dp[i][j] 需要知道 dp[i-1][j]和 dp[i-1][ j-wᵢ ]+vᵢ ，即需要先知道上图红色箭头所指的位置，这样我们便清楚知道了，dp数组应该如何初始化，即绿色箭头所指的列和行。

初始化如下图：

dp数组初始化了，递推公式我们也知道了，后面这个数组自然而然也可以求出来了。

遍历顺序的讨论

上面我们得出dp数组是先遍历物品，再遍历背包容量，那可不可以先遍历背包容量再遍历物品，答案是可以的，但此时 dp[j][i] =Max( dp[ j-wᵢ ][ i-1 ]+vᵢ ,dp[ j ][ i-1 ] )。

而此时 dp数组的含义就是 容量为 j 的背包随机放 0-i 之间的物品，所放物品的最大价值。

代码

• 先遍历物品，再遍历背包

// 01背包问题: weights表示每个物品的重量，values表示每个物品的价值，target表示背包的总容量。求在不超过背包总容量的前提下，这个背包能装载的最大价值的物品是多少
// dp[i][j]=max(dp[i-1][j], dp[i-1][j-w(i)]+v(i))
// 先遍历物品，再遍历背包
func Backpack(weights []int, values []int, target int) int {
	n := len(weights)
	dp := make([][]int, n)
	// 初始化dp
	for i := range dp {
		dp[i] = make([]int, target+1)
		for j := 1; j <= target; j++ {
			if weights[i] <= target {
				dp[i][j] = values[i]
			}
		}
	}
	for i := 1; i < n; i++ {
		for j := 1; j <= target; j++ {
			if weights[i] > j {
				dp[i][j] = dp[i-1][j]
				continue
			}
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]]+values[i])
		}
	}
	return dp[n-1][target]
}

func max(x, y int) int {
	if x > y {
		return x
	}

	return y
}

• 先遍历背包，再遍历物品
  此时dp[i][j]表示容量为i的背包，从[0,j]的商品中选取部分商品，得到的最大价值。dp[i-1][j]表示容量为i-1的背包，从[0,j]的商品中选取部分商品，得到的最大价值。

所以此时递推公式是：dp[i][j]=max(dp[i][j-1],dp[i-w(j)][j-1]+v(j))

// 先遍历背包，再遍历物品：dp[i][j]=max(dp[i][j-1],dp[i-w(j)][j-1]+v(j))
func Backpack1(weights []int, values []int, target int) int {
	n := len(weights)
	dp := make([][]int, target+1)
	// 初始化dp
	for i := range dp {
		dp[i] = make([]int, n)
		if weights[0] <= i {
			dp[i][0] = values[0]
		}
	}
	for i := 1; i <= target; i++ {
		for j := 1; j < n; j++ {
			if weights[j] > i {
				dp[i][j] = dp[i][j-1]
				continue
			}
			dp[i][j] = max(dp[i][j-1], dp[i-weights[j]][j-1]+values[j])
		}
	}
	return dp[target][n-1]
}

先遍历背包再遍历物品有点绕，暂时没看懂可以先跳过去。

一维dp数组

我们在上面知道了 二维数组的递推公式是 dp[i][j]=Max( dp[i-1][j] , dp[i-1][ j-wᵢ ]+vᵢ )。

即dp[i][j] 的值只与上一层的左上方和正上方有关。换句话说只与上一层有关。那我们是不是可以将二维dp数组降为一维dp数组呢？

答案是可以的。

我们可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][ j -wᵢ ] + vᵢ );

与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

递推公式

dp[j] = max(dp[j], dp[j - wᵢ] + vᵢ);

那么如何推导dp[j]呢？

dp[j]可以通过dp[ j - wᵢ ]推导出来，dp[j - wᵢ ]表示容量为j - wᵢ 的背包所背的最大价值。

dp[j - wᵢ ] + vᵢ 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）

此时dp[j]有两个选择，一个是不放物品i ，取自己 dp[j] 相当于 二维dp数组中的dp[i-1][j]，，一个是放物品i 取dp[j - wᵢ ] + vᵢ，然后求两者最大值

初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

那么dp数组除了下标0的位置，初始化为0，其他下标应该初始化多少呢？

看一下递归公式：dp[j] = max(dp[j], dp[j - wᵢ ] + vᵢ );

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

这样才能让dp数组在递归公式的过程中取到最大的价值，而不是被初始值覆盖了。

遍历

我们由上面知道了递推公式为 dp[j] = max(dp[j], dp[j - wᵢ ] + vᵢ )。虽然它是一维数组，但和我们二维递推数组还是很像的，所以想想我前面说的话：

dp[i][j] 的值只与上一层的左上方和正上方有关。

所以我们遍历的时候 应该先遍历物品，再遍历背包容量，并且背包是从大到小倒序遍历。

遍历顺序的讨论

那这个一维数组的两个for循环是否可以颠倒呢？

答案是不可以的。

因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个符合当前容量的最大价值的物品。

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

代码

// 先遍历物品，后遍历背包，而且背包要从大到小
// 递推公式：dp[j]=max(dp[j],dp[j-w(i)]+v(i))
func Backpack2(weights []int, values []int, target int) int {
	dp := make([]int, target+1)
	for i := range weights {
		for j := target; j >= 0; j-- {
			if weights[i] > j {
				continue
			}
			dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
		}
	}
	return dp[target]
}

一维dp看起来容易，理解起来不容易。需要仔细品味。

一维dp虽然难理解，但是它是解决完全背包的关键。下面继续看一下完全背包问题

完全背包

算法题描述

有N种物品和一个容量为V的背包，每种物品都有无限件可用（这也是与01背包的区别）。

第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

思路

这个问题非常类似于01背包问题，所不同的是每种物品有无限件，也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……取[V/c]件等很多种（我们可以想象01背包就是取0件或者1件，所以完全背包其实就是01背包转换过来的）。如果仍然按照解01背包时的思路，令f[v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：

dp[j]=Max(dp[j] , dp[j-w(i)]+v(i))

代码

func Backpack3(weights []int, values []int, target int) int {
	dp := make([]int, target+1)
	for i := range weights {
		for j := weights[i]; j <= target; j++ {
			dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
		}
	}
	return dp[target]
}

可以看到，这个算法和01背包问题中的一维dp非常像，唯一区别就是遍历背包的时候，是正序的。

01背包问题的一维，背包要逆序，其实是先计算大容量背包，这个时候小容量的背包是上一次的结果。也就是上一行的值。

而完全背包问题中，背包正序，计算当前背包的时候，用的是前面的背包容量，也就是当前行的值。

这是正序和逆序的区别。

总结

本文介绍了01背包问题的dp解法，有二维dp和一维dp。

• 二维dp可以先遍历物品后遍历背包，也可以先遍历背包后遍历物品
• 一维dp只能先遍历物品后遍历背包，而且背包要从大到小遍历

还介绍了完全背包问题。

• 完全背包的一维dp可以先遍历物品后遍历背包，也可以先遍历背包后遍历物品

一维dp虽然难以理解，但是它能解决01背包和完全背包问题。

参考

[1]背包问题——01背包|完全背包

br>