背包问题
# 背包问题
参考背包问题九讲，对 01 背包问题和完全背包问题进行学习。
# 1. 01 背包问题
# 1.1 题目
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品消耗的费用是 Ci，得到的价值是 Wi，求解讲哪些物品装入背包可以使价值总和最大。
# 1.2 基本思路
这是最基本的背包问题，特点：每种物品仅有一件，可以选择放或不妨。
用子问题定义状态：F[i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其转移方程便是：
$$ F[i,v]=max{F[i-1,v],F[i-1,v-C_i]+W_i} $$
这个方程十分重要，基本上所有的背包相关的问题的方程都是由它衍生出来的。解释一下：“将前 i 件物品放入容量为 v 的背包中” 这个子问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只和前 i-1 件物品相关的问题。如果不放第 i 件物品，那么问题就转化为 ”前 i-1 件物品放入容量为 v 的背包中“，价值为 F[i-1,v]；如果放第 i 件物品，那么问题就转化为 ”前 i-1 件物品放入剩下的容量为 v-Ci 的背包中“，此时能获得的最大价值就是 F[i-1,v-Ci] 再加上通过放入第 i 件物品获得的价值 Wi。
根据基本思路写出的代码：
/**
* 01背包问题解法
* @param c 每个物品的体积,cost
* @param w 每个物品的价值,worth
* @param v 背包的容积
* @return 最大价值
*/
public static int knapsackProblem01(int[] c, int[] w, int v) {
int n = c.length; // 物品数量
int[][] dp = new int[n + 1][v + 1];
for (int i = 1; i <= n; i++) { // 先循环物品
for (int j = 0; j <= v; j++) { // 再循环容量
dp[i][j] = dp[i - 1][j]; // 不选第i件物品
if (j >= c[i - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - c[i - 1]] + w[i - 1]); // 选第i件物品
}
}
}
return dp[n][v];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 1.3 优化空间复杂度
以上方法的时间和空间复杂度均为 O(VN)，其中时间复杂度不能再优化了，但是空间复杂度却可以优化到 O(V)。
需要考虑，如果只用一个一维数组，能不能保证第 i 次循环结束后 F[v] 中表示的就是我们定义的状态 F[i, v] 呢？F[i, v] 是由 F[i-1, v] 和 F[i-1,v-Ci] 两个子问题递推而来，能否保证再推 F[i, v] 时能够取用 F[i-1, v] 和 F[i-1,v-Ci] 的值呢？只要保证 v 的循环为递减顺序，就可以保证计算 F[v] 时 F[v-Ci] 保存的时状态 F[i-1,v-Ci] 的值。
优化代码如下：
/**
* 01背包问题解法
* @param c 每个物品的体积,cost
* @param w 每个物品的价值,worth
* @param v 背包的容积
* @return 最大价值
*/
public static int knapsackProblem01(int[] c, int[] w, int v) {
int n = c.length; // 物品数量
int[] dp = new int[v + 1];
for (int i = 1; i <= n; i++) { // 先循环物品
for (int j = v; j >= 0; j--) { // 再循环容量
if (j >= c[i - 1]) {
dp[j] = Math.max(dp[j], dp[j - c[i - 1]] + w[i - 1]); // 选第i件物品
}
}
}
return dp[v];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
注意：容量的遍历一定要从后往前遍历，因为再计算 F[v] 时需要 F[v-Ci] 的值，也就是后面的值依赖于前面的值。
# 1.4 初始化细节
背包问题中有两种不同的问法。有的题目要求”恰好装满背包“时的最优解，有的没有要求装满。区别两种问法的实现时再初始化的适合有所不同。
- 如果要求恰好装满背包，那么初始化时除了 F[0] 为 0，其他 F[1:V] 均设为负无穷，这样就可以保证最终得到的 F[V] 是一种恰好装满背包的最优解。
- 如果没有要求装满背包，那么初始化时将 F[0:V] 全部设为 0。
理解：初始化 F 数组事实上就是在没有物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装的情况下被恰好装满，其他容量的背包均没有合法解，应该被赋值为负无穷。如果背包非必须被装满，那么任何容量的背包都由一个合法解，所以初始化时状态的值也就全部为 0。
# 2 完全背包问题
# 2.1 题目
有 N 件物品和一个容量为 V 的背包，每种物品都有无限个。放入第 i 件物品消耗的费用是 Ci，得到的价值是 Wi，求解讲哪些物品装入背包可以使价值总和最大。
# 2.2 基本思路
这个问题非常类似于 01 背包问题，所不同的时每种物品由无限件。也就是从物品的角度考虑，与它相关的策略已并非取或不取两种，而是取 0 件，取 1 件，取 2件……直至取 [V/Ci] 件等。
如果仍然按照 01 背包时的思路，令 F[i, v] 表示前 i 种物品放入一个容量为 v 的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
$$ F[i,v]=max{F[i-1,v-kC_i]+W_i | 0\leq kC_i \leq v} $$
这跟 01 背包问题一样有 O(VN) 个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态 F[i,v] 的时间是 O(v/Ci)，总的复杂度可以认为是 O(NVΣv/Ci)，是比较大的。
# 2.3 优化
- 若两件物品 i 和 j 满足 Ci <= Cj 且 Wi >= Wj ，那么可以直接去掉 j 物品。
- 直接去掉体积大于 V 的物品。
# 2.4 转化为 01 背包问题求解
完全背包问题的代码可以由 01 背包问题（一维数组）的代码简单转化而来。
01 背包问题按照 v 递减的次序来循环，让 v 递减是为了保证第 i 次循环的状态 F[i, v] 是由 F[i-1, v] 和 F[i-1,v-Ci] 递推而来。换句话说，这正是为了保证每间物品只选一次，保证在考虑 ”选入第 i 件物品“ 这件策略时，依据的是一个未选择第 i 件物品的子结果 F[i-1,v-Ci]。
而完全背包问题的特点时每种物品可以选无限件，所以在考虑 "加选第 i 件物品" 这种策略时，正需要一个可能已选入第 i 种物品的子结果 F[i,v-Ci]，所以必须采用 v 递增的顺序取循环。
同时可以颠倒两层 for 循环获得算法时间常数上的优化。
代码：
/**
* 完全背包问题解法
* @param c 每个物品的体积,cost
* @param w 每个物品的价值,worth
* @param v 背包的容积
* @return 最大价值
*/
public static int knapsackProblemAll(int[] c, int[] w, int v) {
int n = c.length; // 物品数量
int[] dp = new int[v + 1];
for (int j = 0; j <= v; j--) { // 循环容量
for (int i = 1; i <= n; i++) { // 循环物品
if (j >= c[i - 1]) {
dp[j] = Math.max(dp[j], dp[j - c[i - 1]] + w[i - 1]); // 选第i件物品
}
}
}
return dp[v];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19