【刷题日记】背包问题

背包问题已经是一个很经典而且讨论很广泛的算法问题了。

背包问题泛指这类种问题： 给定一组有固定价值和固定重量的物品， 以及一个已知最大承重量的背包， 求在不超过背包最大承重量的前提下， 能放进背包里面的物品的最大总价值。

具体各类背包问题可以分成以下不同的子问题。

不同的背包问题

0-1 背包问题

特点：每个物品只有一件，选择放或者不放。

变形 1：存在最大容量 - 求最大价值

0-1 背包问题案例：🟨 125 · 背包问题（二） - LintCode

有 n 个商品，第 i 个商品价值 $v_i$ 元，重 $w_i$ 千克，$v_i$ 和 $w_i$ 都是整数。背包最多容纳 W 千克（整数）商品，每个商品要么全拿走，要么不拿走，我们需要拿走商品的总价值最高。

dp[i][j] 表示前 i 个商品在 j 空间下的最优选择的价值。

这里的模型为：

$$dfs(i,c) = \max (dfs(i-1,c),dfs(i-1,c-w[i])+v[i])$$

我们可以使用动态规划算法：

// 给定数组 `a` 表示每个物品的大小和数组 `v` 表示每个物品的价值.
public int backPackII(int W, int[] a, int[] v) {
	int len = a.length;
	// 数组dp[i][j]表示从前i件物品选体积不超过j的物品最大价值
	int[][] dp = new int[W+1][len+1]; // 初始化其首行首列的值为0
	// 【不同写法】内外循环是可以调换的
	for(int i=1;i<=W;i++){            // 【高效】从1开始。从0也行，但低效
		for(int j=0;j<len;j++){       // 【不同写法】可以从0或从1开始
			if(a[j]<=i){
				dp[i][j+1] = Math.max(dp[i][j],dp[i-a[j]][j]+v[j]);
			}else{
				dp[i][j+1] = dp[i][j];
			}
		}
	}
	return dp[W][len];
}

复杂度分析：

• 时间复杂度： $O(nW)$。
• 空间复杂度： $O(nW)$。

不同循环写法的优劣

问：两层循环有两种写法，一种是外层循环枚举物品，内层循环枚举体积；另一种是外层循环枚举体积，内层循环枚举物品。如何评价这两种写法的优劣？

答：两种写法都可以，但更推荐前者。外层循环枚举物品的写法，只会遍历物品数组一次；而内层循环枚举物品的写法，会遍历物品数组多次。从 cache 的角度分析，多次遍历数组会导致额外的 cache miss，带来额外的开销。所以虽然这两种写法的时间空间复杂度是一样的，但外层循环枚举物品的写法常数更小。

滚动数组优化空间复杂度至 $2*W$：

public int backPackII(int W, int[] a, int[] v) {
	int len = a.length;
	int[][] dp = new int[W+1][2];
	for(int j=0;j<len;j++){
		for(int i=1;i<=W;i++){   // 【不同写法】此处循环可以正序或者逆序
			if(a[j]<=i){
				dp[i][(j+1)%2] = Math.max(dp[i][j%2],dp[i-a[j]][j%2]+v[j]);
			}else{
				dp[i][(j+1)%2] = dp[i][j%2];
			}
		}
	}
	return dp[W][len%2];
}

复杂度分析：

• 时间复杂度： $O(nW)$。
• 空间复杂度： $O(W)$。

注意到，对于物品空间的遍历（也就是上面代码的内层循环），循环顺序不影响结果。我们可以进一步考虑只使用一维 dp 数组。

public int backPackII(int W, int[] a, int[] v) {
	int len = a.length;
	int[] dp = new int[W+1];
	for(int j=0;j<len;j++){
		for(int i=W;i>=0;i--){
			// 【优化点】if-else语句可优化
			if(a[j]<=i){
				dp[i] = Math.max(dp[i],dp[i-a[j]]+v[j]);
			}else{
				dp[i] = dp[i];
			}
		}
	}
	return dp[W];
}

注意，0-1 背包使用一维数组时，内层循环只能逆序遍历！逆序遍历时，新值取自上一轮的旧值，所以不会有什么影响。

对 if-else 语句进行优化，得到最终的 0-1 背包一维数组写法：

public int backPackII(int W, int[] a, int[] v) {
	int len = a.length;
	int[] dp = new int[W+1];
	for(int j=0;j<len;j++){
		for(int i=W;i>=a[j];i--){
			dp[i] = Math.max(dp[i],dp[i-a[j]]+v[j]);
		}
	}
	return dp[W];
}

复杂度分析：

• 时间复杂度： $O(nW)$。
• 空间复杂度： $O(W)$。

相关题目：

• 🟨 474. 一和零 - 力扣（LeetCode） 二维背包
• 🟨1049. 最后一块石头的重量 II - 力扣（LeetCode）

变形 2：恰好装满容量 - 求方案数

如果题目要求背包恰好装满，求方案数，这时 dp 边界条件和状态转移公式有些许不同。这里展示最普通的二维数组写法。一维数组写法可自行尝试。

int[][] dp  = new int[W+1][nums.length+1];
dp[0][0]=1; // 边界条件
for(int i=0;i<=W;i++){ //【注意】强烈建议从0开始
	for(int j=0;j<nums.length;j++){
		if(i>=nums[j]){
			dp[i][j+1] = dp[i][j]+dp[i-nums[j]][j];
		}else{
			dp[i][j+1] = dp[i][j];
		}
	}
}

有时候，给定的物品中会存在重量为 0 的物品，这时候外层循环中一定要从 0 开始。

相关题目：

• 🟨 494. 目标和 - 力扣（LeetCode）
• 🟥 LCP 47. 入场安检 - 力扣（LeetCode）

变形 3：恰好装满容量 - 求可行性

假设题目要求我们回答给定的物品能否在指定的空间 W 恰好装满，我们可以有两种方式思考。

第一种思路是，将题目转变为「变形 1：存在最大容量 - 求最大价值」，最后判断一下最大价值是否是最大容量即可。

int W = sum/2;
int len = nums.length;
int[][] dp = new int[W+1][len+1];
for(int i=1;i<=W;i++){
	for(int j=0;j<len;j++){
		if(nums[j]<=i){
			dp[i][j+1] = Math.max(dp[i][j],dp[i-nums[j]][j]+nums[j]);
		}else{
			dp[i][j+1]=dp[i][j];
		}
	}
}
return dp[W][len]==W;

第二种思路是使用布尔 dp。我们需要重新考虑状态转移方程。

int W = sum/2;
int len = nums.length;
boolean[][] dp = new boolean[W+1][len+1];
dp[0][0]=true;
for(int i=0;i<=W;i++){ // 【注意】从0开始
	for(int j=0;j<len;j++){
		if(nums[j]<=i){
			dp[i][j+1] = dp[i][j]|dp[i-nums[j]][j];
		}else{
			dp[i][j+1]=dp[i][j];
		}
	}
}
return dp[W][len];

相关题目：

• 🟨 416. 分割等和子集 - 力扣（LeetCode）

完全背包问题

特点：每个物品可以无限选用

变种 1：存在最大容量 - 求最大价值

完全背包问题案例

有编号分别为 a,b,c,d 的四件物品， 它们的重量分别是 2,3,4,7， 它们的价值分别是 1,3,5,9， 每件物品数量无限个， 现在给你个承重为 10 的背包， 如何让背包里装入的物品具有最大的价值总和？

这里的模型为：

$$dfs(i,c) = \max (dfs(i-1,c),dfs(i,c-w[i])+v[i])$$

注意点：

• 和 0-1 背包不一样的是，状态转移方程中再进行「选」处理时，考察的背包空间为 i 而不是 i-1，这体现了完全背包的无限物品取用。
• 不要尝试激进贪心，将状态方程转写为 dfs(i,c) = max(dfs(i-1,c),dfs(i,c%w[i])+v[i]*c/w[i])。这种方法可能会导致余数可能无法被其他物品组合，导致无效解，且不能保证所有可能的组合都被覆盖。

变种 2：恰好装满容量 - 求方案数

二维 dp 示例写法：

int len = nums.length;
int[][] dp = new int[W+1][len+1];
dp[0][0]=1;
// 【不同方法】内外循环可以调换
for(int i=0;i<=W;i++){
	for(int j=0;j<len;j++){
		if(nums[j]<=i){
			dp[i][j+1] = dp[i][j]+dp[i-nums[j]][j+1];
		}else{
			dp[i][j+1] = dp[i][j];
		}
	}
}
return dp[W][len];

一维 dp 示例写法：

int len = nums.length;
int[] dp = new int[W+1];
dp[0]=1;
for(int j=0;j<len;j++){
	for(int i=nums[j];i<=W;i++){ // 【注意】内层循环为顺序遍历
		dp[i] = dp[i]+dp[i-nums[j]];
	}
}
return dp[W];

注意，完全背包问题使用 1 维 dp 数组时，内层循环只能使用顺序遍历！想要理解这个过程可以看后文我画的示意图。

相关题目：

• 🟨 518. 零钱兑换 II - 力扣（LeetCode）

变种 3：恰好装 capacity，求最小价值

一维 dp 示例写法：

int len = nums.length;
int[] dp = new int[W+1];
int max = W; // max 值为最大值。视题目而定，有时候是不可能的大值。
Arrays.fill(dp,max); // 【重要】初始化大值
dp[0]=0; // 【重要】含义为W=0时不需要任何物品，因此价值为0
for(int j=0;j<len;j++){
	for(int i=nums[j];i<=W;i++){
		dp[i] = Math.min(dp[i],dp[i-nums[j]]+1);
	}
}
return dp[W];

相关题目：

• 🟨 322. 零钱兑换 - 力扣（LeetCode）
• 🟨 279. 完全平方数 - 力扣（LeetCode）

分组背包问题

给你 N 组物品，然后每一组你至多选择一个物品（也可以不选），每个物品都有自己的体积和价值，现在给你一个容里为 M 的背包，让你用这个背包装物品，使得物品价值总和最大。

相关题目：

• 🟨 1155. 掷骰子等于目标和的方法数 - 力扣（LeetCode）

依赖背包问题

一棵树有 N 个节点，每一个节点放有一个物品，这些物品有自己的体积和价值。如果你要选择 v 节点的物品，那么必须先选择 v 的父亲节点上的物品（所谓的依赖关系）。现在你有容里为 M 的背包，问你选择物品的最大权值和是多少。

多重背包问题

特点：每个物品都有一定的数量限制的选取。

例子

有编号分别为 a,b,c 的三件物品， 它们的重量分别是 1， 2， 2， 它们的价值分别是 6， 10， 20， 他们的数目分别是 10， 5， 2， 现在给你个承重为 8 的背包， 如何让背包里装入的物品具有最大的价值总和？

相关题目：

• 🟥 2585. 获得分数的方法数 - 力扣（LeetCode）

分数背包问题（零头背包）

有 n 个商品，第 i 个商品价值 $v_i$ 元，重 $w_i$ 千克，$v_i$ 和 $w_i$ 都是整数。背包最多容纳 W 千克（整数）商品，对于每个商品，我们可以拿走其中一部分。我们需要拿走商品的总价值最高。

贪心策略：尽量多的拿走每千克价值最高的商品。

总结：动态规划中的背包问题

DP 数组的压缩

当 dp 数组压缩为一维数组时，遍历顺序：

• 0-1 背包为倒序遍历
• 完全背包为正序遍历

背包问题常见变形

变形：

• 至多装 capacity，求方案数/最大价值和
• 恰好装 capacity，求方案数/最大/最小价值和
• 至少装 capacity，求方案数/最小价值和

递推公式中的符号问题：

• 方案数：用加法（加法原理）
• 最大最小值：用最大最小值函数

背包问题的解决方法

解决方法有：

• 动态规划
• 贪心算法
• 回溯法：先确定解空间的结构， 使用深度优先搜索， 搜索路径一般沿树形结构进行， 在搜索过程中， 首先会判断所搜索的树结点是否包含问题的解， 如果肯定不包含， 则不再搜索以该结点为根的树结点， 而向其祖先结点回溯； 否则进入该子树， 继续按深度优先策略搜索。运用回溯法解题通常包含以下三个步骤：
  1. 针对所给问题， 定义问题的解空间；
  2. 确定易于搜索的解空间结构；
  3. 以深度优先的方式搜索解空间， 并且在搜索过程中用剪枝函数避免无效搜索；

• 分支限界法：分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。分支限界法首先要确定一个合理的限界函数（bound funciton），并根据限界函数确定目标函数的界 [down ,up]，按照广度优先策略或以最小耗费优先搜索问题的解空间树，在分支结点上依次扩展该结点的孩子结点，分别估算孩子结点的目标函数可能值，如果某孩子结点的目标函数可能超出目标函数的界，则将其丢弃；否则将其加入待处理结点表（简称 PT 表），依次从表 PT 中选取使目标函数取得极值的结点成为当前扩展结点，重复上述过程，直到得到最优解。常见的两种分枝限界法包含队列式（FIFO）分支限界法和优先队列式分支限界法。

【待理解与整理】用分支限界法解决 0-1 背包问题

假设比值 pi/wi 最大的物品序号为 s（s ∈ S3），按照价值重量比递减排序后，s 就是集合 S3(k) 中的第一个元素。用 s 进行分支，一个分支结点表示把 s 装入背包，另一个分支结点表示不把 s 装入背包。

1. 设置上界估算方法 b(k)
   假定 b(k) 表示在搜索深度为 k 时，某个分支结点的背包中商品的价值上界。此时 S3(k) = {k, k+1, …, n-1}。
   
2. 利用分支限界法求解：
   第一步，初始化 bound = 0，把物品按价值重量比递减排序，建立根节点 X；
   第二步，建立新结点，计算新结点的上界，与 bound 进行比较，据此判定是否插入优先队列，直到当前尚待选择的物品集合为空时，找到一个可行解，判定是否更新 bound；
   第三步，同样操作建立另外一个新结点 Z；第四步，取出优先队列首元素作为根结点 X，第四步，如此往复直到搜索深度为所有物品数量为止。

本文参考

• 我的笔记
• 《算法导论》动态规划、贪心策略部分解耦
• 研究生课程《算法设计与分析》实验五：0-1 背包问题的算法设计
• 0-1背包 完全背包【基础算法精讲 18】_哔哩哔哩_bilibili
• 背包问题----分组背包(超详细讲解)-CSDN博客
• 0-1背包详解-CSDN博客
• 分支限界法——对解空间的一种策略搜索（广度优先搜索） - 简书