更多算法相关内容请关注「宫水三叶的刷题日记」
前言
本文将从最简单的 0-1 背包问题出发，讲解如何将相应解法从 $O(N * C)$ 的空间复杂度降到 $O(C)$ 。
在使用一维数组解决 0-1 背包问题的基础上，讲解如何解决完全背包、多重背包、分组背包、背包具体方案 和 有依赖的背包问题 ...
0-1 背包问题
0-1 背包问题 ：有 N 件物品和一个容量为 C 的背包。第 i 件物品的费用是 v[i]，价值是 w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
0-1 背包问题是众多背包问题中最简单的，其特点是物品不能重复放入。
定义状态：即 f[i][C] 表示前 i 件物品放入一个容量为 C 的背包可以获得的最大价值。
状态转移方程为：
f[i][C]=max(f[i−1][C],w[i]+f[i−1][C−v[i])
即对于第 i 件物品，我们有两种决策方案：
不选择第 i 件物品，则最大价值等于 f[i - 1][C] ，全部容量留给前 i - 1 件物品
选择第 i 件物品，则最大价值等于 w[i] + f[i - 1][C - v[i]] ，其中 w[i] 代表当前物品的价值，这样就用掉了 v[i] 的体积，留给前 i - 1 件物品的容量就剩下 C - v[i]，所以总的价值等于 w[i] + f[i - 1][C - v[i]]
0-1 背包问题的 dp[N][C + 1] 解法
根据状态转移方程，我们可以建立一个二维的 dp 数组来存储结果。
第一维代表物品的下标（范围从 0 到 N - 1），第二维代表了容量的变化（范围从 0 到 C）。
并得知 base case dp[0][0] 的初始值为 0，原问题的解在 dp[N - 1][C] 的格子里面。
import java.util.Scanner;public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); } System.out.println(maxValue(N, C, v, w)); }
private static int maxValue(int N, int C, int[] v, int[] w) { int[][] dp = new int[N][C + 1]; dp[0][0] = 0; for (int i = 0; i < C + 1; i++) { dp[0][i] = i >= v[0] ? w[0] : 0; } for (int i = 1; i < N; i++) { for (int j = 0; j < C + 1; j++) { int n = dp[i - 1][j]; // 不选该物品 int y = 0; if (j >= v[i]) { y = w[i] + dp[i - 1][j - v[i]]; // 选择该物品 } dp[i][j] = Math.max(n, y); } } return dp[N - 1][C]; }}
复制代码
该算法的时空复杂度均为 $O(N * C)$ 。
我们使用的「动态规划」本质也是一种枚举，所以在时间复杂度上已经没有优化空间了（枚举需要对每一种可能性进行统计）。
0-1 背包问题的 dp[2][C + 1] 解法
根据状态转移方程，我们可以知道计算某个格子的值，只需要依赖前一行（计算第 i 行格子只需要第 i - 1 行中的某些值）。
所以可以用一个只有两行的数组来存储中间结果，根据当前计算的行号是偶数还是奇数来交替使用第 0 行和第 1 行。
import java.util.Scanner;public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); } System.out.println(maxValue(N, C, v, w)); }
private static int maxValue(int N, int C, int[] v, int[] w) { int[][] dp = new int[2][C + 1]; dp[0][0] = 0; for (int i = 0; i < C + 1; i++) { dp[0][i] = i >= v[0] ? w[0] : 0; } for (int i = 1; i < N; i++) { for (int j = 0; j < C + 1; j++) { int n = dp[(i - 1)%2][j]; // 不选该物品 int y = 0; if (j >= v[i]) { y = w[i] + dp[(i - 1)%2][j - v[i]]; // 选择该物品 } dp[i%2][j] = Math.max(n, y); } } return dp[(N - 1)%2][C]; }}
复制代码
这样我们就把算法的空间复杂度从 $O(N * C)$ 降低为 $O(C)$。
再次观察状态转移方程，我们发现当求解第 i 行格子的值的时候，不仅是只依赖第 i - 1 行，而且是明确只依赖第 i - 1 行的第 C 个格子和第 C - v[i] 个格子（也就是对应着第 i 个物品不选和选的两种情况）。
0-1 背包问题的 dp[C + 1] 解法
也就是说明确只依赖于 「上一个格子的位置」 以及 「上一个格子的左边位置」。
当我们将求解第 i 行格子顺序从 0 到 C 改为从 C 到 0，我们可以将原本 2 行的二维数组压缩到一行（转换为一维数组）。
import java.util.Scanner;public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); } System.out.println(maxValue(N, C, v, w)); }
private static int maxValue(int N, int C, int[] v, int[] w) { int[] dp = new int[C + 1]; for (int i = 0; i < C + 1; i++) { dp[i] = i >= v[0] ? w[0] : 0; } for (int i = 1; i < N; i++) { for (int j = C; j >= 0; j--) { int n = dp[j]; // 不选该物品 int y = 0; if (j >= v[i]) { y = w[i] + dp[j - v[i]]; // 选择该物品 } dp[j] = Math.max(n, y); } } return dp[C]; }}
复制代码
这样，当我们处理第 i 行的第 j 个格子的时候，访问的 dp[j] 和 dp[j - v[i]] 其实是第 i - 1 行的结果。
然后通过比较之后，选择当中的最大值更新到 dp[j]，这时候才代表第 i 行第 j 个格子被更新了。
这就是我们使用一维数组解决 0-1 背包问题的解法。
它的时间复杂度仍然是 $O(N * C)$，但空间复杂度已经降为了 $O(C)$。
和 0-1 背包问题的 dp\[2][C + 1] 解法 的空间复杂度一样，都是 $O(C)$，但是相应的常数降低了，从 2C 降为 C。
使用的是一维 dp，在处理第 i 行之前，数组装的都是第 i - 1 行的结果，所以可以对循环内部的判断进行简化：
import java.util.Scanner;public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); } System.out.println(maxValue(N, C, v, w)); }
private static int maxValue(int N, int C, int[] v, int[] w) { int[] dp = new int[C + 1]; for (int i = 0; i < N; i++) { for (int j = C; j >= v[i]; j--) { int n = dp[j]; // 不选该物品 int y = w[i] + dp[j - v[i]]; // 选择该物品 dp[j] = Math.max(n, y); } } return dp[C]; }}
复制代码
当 j 不满足 j >= v[i] 的时候，注定无法选择第 i 个物品，这时候的 dp[i] 应该是等于 dp[i - 1]。
因为使用的是一维数组，dp[i] 本身就是装着 dp[i - 1] 的值，所以无须再进行修改。
这和使用二维 dp 的方式不同，使用二维 dp 就算当前 j 比 v[i] 要小，也要把上一行的 dp[i - 1][j] 的结果拉下来，赋值给 dp[i][j] 。
同时也是因为使用的是一维 dp，没有了访问 dp[i - 1][j] 这样的操作，也不需要先处理第 0 行，可以直接让循环从 i = 0 开始。
如何用一维 dp 来解决 0-1 背包十分重要，其他背包问题一定程度上都能转化成 0-1 背包来进行求解 或是 根据 0-1 背包的转移方程来稍作修改。
完全背包问题
完全背包问题 ： 有 N 种物品和一个容量为 C 的背包，每种物品都有无限件。
第 i 件物品的体积是 v[i]，价值是 w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
其实就是在 0-1 背包问题的基础上，增加了每件物品可以选择多次的特点（在容量允许的情况下）。
状态转移方程 & 时间复杂度分析
根据和 0-1 背包问题的基本思路，我们可以写成如下的状态转移方程：
f[i][C]=max(f[i−1][C−kv[i]]+kw[i]),0<=k∗v[i]<=c
该式子很好理解，k * v[i] 为 0 的时候代表不选当前的第 i 件物品，这时候有 f[i][C] = f[i - 1][C] ，当 k * v[i] 不为 0 的时候，代表第 i 件物品可能会被选择多次。
这时候二维 dp 的表格大小依然是 *N * C* 的，但是求解某个格子的值的时候，并不是单纯的比较上一行的两个格子，而是要比较多个格子。
要比较的格子数量不确定，比较格子的数量等于最多可选第 i 件物品多少次，也就是 (C / v[i]) + 1 个。
这里的 C 为当前格子的容量，不是总容量，加一代表还要比较不选择第 i 个格子的情况），按照最坏的时间复杂度计算，最多要比较 C + 1 个格子，也就是上一行的 0 ~ C 的格子全部都要进行比较。
这时候计算某个格子的值不再是常数操作。时间复杂度为 $O(N C C)$ 。
完全背包问题的常规解法
import java.util.Scanner;public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); } System.out.println(maxValue(N, C, v, w)); }
private static int maxValue(int N, int C, int[] v, int[] w) { int[] dp = new int[C + 1]; for (int i = 0; i < N; i++) { for (int j = C; j >= v[i]; j--) { for (int k = 0 ;; k++) { if (j < v[i] * k) { break; } dp[j] = Math.max(dp[j], dp[j - v[i] * k] + w[i] * k); } } } return dp[C]; }}
复制代码
我们在处理第 j 个格子的时候，某件物品可以不选或者选到超出容量限制为止（反映了完全背包问题物品可以选择无限次的特点）。由此我们得出了完全背包问题的常规解法，它的时间复杂度是大于 $O(N * C)$ 的。
利用 0-1 背包的一维 dp 方法求解完全背包
我们掌握了如何通过一维 dp 解决 0-1 背包问题，只需要将求解第 i 行格子（逻辑上的第 i 行，物理上是一维的）的顺序从 C 到 0 改回从 0 到 C 即可。
import java.util.Scanner;public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); } System.out.println(maxValue(N, C, v, w)); }
private static int maxValue(int N, int C, int[] v, int[] w) { int[] dp = new int[C + 1]; for (int i = 0; i < N; i++) {
// for (int j = C; j >= v[i]; j--) { // 0-1 背包问题 for (int j = v[i]; j <= C; j++) { // 完全背包问题
int n = dp[j]; // 不选该物品 int y = w[i] + dp[j - v[i]]; // 选择该物品 dp[j] = Math.max(n, y); } } return dp[C]; }}
复制代码
将 j 的处理顺序改为从小到大，这样就保证当我们使用 dp[j - v[i]] 时，该值是已经被计算过的。
这样所代表的状态含义是：当在容量为 j 的时候，考虑将 i 物品加入，剩余的 j - v[i] 容量也考虑加入物品 i（反映了完全背包问题的物品是可以被重复选择的特点）。
完全背包问题的一维 dp 解法的数学证明
前面所说的「将 j 的处理顺序改为从小到大，这样就保证当我们使用 dp[j - v[i]] 时，该值是已经被计算过的」，是我们利用抽象思维去理解这样的做法。
但感觉不一定是对的。
我们尝试从数学的角度去证明为什么 dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i] 在完全背包问题中是正确的。
首先我们将状态转移方程退回去最朴素的二维解法中。
也就是用一维代表当前决策的是前 i 个物品，用一维代表当前的容量为 j。这时候根据完全背包中物品的选择次数是无限的。
可以得出：
dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i],dp[i−1][j−2v[i]]+2w[i]...dp[i−1][j−kv[i]+kw[i]]),0<=k∗v[i]<=j
dp[i][j] 对应的就是：面对第 i 件物品，可以不选，可以选 1 次，可以选 2 次 ...
在容量允许的情况下，不失一般性的可以选 k 次 ...
然后再来看看 dp[i][j - v[i]] 是什么内容：
dp[i][j−v[i]]=max(dp[i−1][j−v[i]],dp[i−1][j−2v[i]]+w[i],dp[i−1][j−3v[i]]+2w[i]...dp[i−1][j−kv[i]+(k−1)w[i]]),0<=kv[i]<=j
光看公式可能很难看出两者的联系，我们将相同的部分进行标记：
总结一下，0-1 背包问题的状态转换方程是 1，完全背包问题的状态转移方程是 2：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
两者仅仅是 dp[i - 1][j - v[i]] 和 dp[i][j - v[i]] 的区别，这一区别决定了 j 的遍历顺序。
虽然完全背包问题的实现上和 0-1 背包相比，只是在对 j 的遍历方向上进行修改。
但能这样做原因是因为有严谨的数学证明推导，而不是凭感觉抽象理解。
彻底转换为 0-1 背包问题
对于完全背包，我们知道每件物品可以选择无限次，但是我们的容量仍然是有限的。
这就意味着对于每件物品而言，我们选择范围为 0~C/v[i]，要么一件不选，要么所有容量都用来装这同一件物品。
我们可以新建一个物品数组，对于第 i 件物品，往物品数组放入 C/v[i] 件，第 i + 1 件物品，则放入 C/v[i + 1] 件 ...
从而将一个完全背包问题彻底转换为 0-1 背包问题。
这样的做法不会降低我们的复杂度，反而增加了我们转换背包问题时所带来的常数级别的复杂度成本，所以不对该做法进行展开。
我们是可以采用「二进制数」的思路来优化，但它优化完的复杂度仍然是大于 $O(N * C)$ 的，所以我们将这个优化思路放到「多重背包问题」里去讲。
这样的做法仍然很有意义，它给我们提供了一个思路：将一种物品拆成多件物品，从而将其他背包问题彻底转换为 0-1 背包进行求解。
多重背包问题
多重背包问题 I ：有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 s[i] 件，每件体积是 v[i]，价值是 w[i]。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
其实就是在 0-1 背包问题的基础上，在容量允许的情况下，增加了每件物品可以选择多次的特点（但又不是无限次，是有限制的多次）。
所以我们还是在 0-1 背包的基础上进行分析。
状态转移方程 & 时间复杂度分析
既然对每件物品有选择数量上的限制，这意味着选择的数量 k 需要满足 0 <= k <= s[i]。
能够很清晰的分析出状态转移方程：
f[i][C]=max(f[i−1][C−kv[i]]+kw[i]),0<=k∗v[i]<=C,0<=k<=s[i]
将 s[i] 按照最坏复杂度计算，这时候算法复杂度应该是 $O(N C C)$。
多重背包问题的常规解法
我们可以基于 0-1 背包问题的一维 dp 解法，增加一个循环，从 0 开始遍历 s[i]。
得出以下的常规解法：
import java.util.Scanner;class Main { public static void main(String[] arg) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; int[] s = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); s[i] = sc.nextInt(); } System.out.println(maxValue(N, C, s, v, w)); }
private static int maxValue(int N, int C, int[] s, int[] v, int[] w) { int[] dp = new int[C + 1]; for (int i = 0; i < N; i++) { for (int j = C; j >= v[i]; j--) { for (int k = 0; k <= s[i] && j >= k * v[i]; k++) { dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]); } } } return dp[C]; }}
复制代码
多重背包问题的「二进制优化」解法
多重背包问题 II ：题目和「多重背包问题 I」完全一样，只是数据范围从 百级 上升到 千级 。
所谓的「二进制优化」其实是指，我们如何将一个多重背包问题彻底转化为 0-1 背包问题，同时降低其复杂度。
0-1 背包问题讲的是物品列表里面的每个物品只能选择一次，而这里的多重背包问题则是每个物品有最大数量限制，所以我们可以将其进行「扁平化」。
如果第 i 件物品有 s1 件，则将 s1 个 i 物品放到物品列表；如果第 i + 1 件物品有 s2 件，则将 s2 件 i + 1 物品放到物品列表。
物品列表里面的每个物品有选和不选两种选择，这样就对应了多重背包问题中的每样物品可以不选或最多选择 s[i] 的特性。
从而将一个多重背包问题彻底转换为 0-1 背包问题。
但是光进行这样的「扁平化」并不能降低算法的复杂度。
因为我们仍然要处理这么多的物品，反而增加了将物品「扁平化」的工作量。
算法的复杂度在常数级别上是上升的。这样做的意义在哪？
我们现在采取的「扁平化」策略是直接展开，一个数量为 10 的物品等效于 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 。
这样并没有减少运算量，但是如果我们能将 10 变成小于 10 个数，那么这样的「扁平化」就是有意义的。
学过 Linux 的都知道文件权限最高是 7，代表拥有读、写、执行的权限。
但其实这个 7 是对应了 1、2、4 三个数字的，也就是 r : 1、w : 2、x : 4 ，三种权限的组合共有 8 种可能性。
这里就采用了 3 个数来对应 8 种情况的“压缩”方法。我们也可以借鉴这样的思路，将原本为 n 的物品用 ceil(log(n)) 个数来代替。从而降低算法复杂度。
7 可以用 1、2、4 来代替，像刚刚提到的 10 ，我们可以使用 1、2、4、3 来代替，你可能会有疑问，为什么是 1、2、4、3，而不是 1、2、4、6 或者 1、2、4、8 呢？
其实把他们几个数加起来就知道了，1、2、4、6 可以表达的范围是 0~13，而 1、2、4、8 可以表达的范围是 0~15，而我们要求的是表达 10，大于 10 的范围是不能被选择的。
所以我们可以在 1、2、4 （表达的范围是 0~7）的基础上，增加一个数 3（由 10 - 7 而来），这样就能满足我们需要表达的范围 0~10。
来看看通过「扁平化」来解决多重背包问题的代码：
import java.util.*;class Main { public static void main(String[] arg) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; int[] s = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); s[i] = sc.nextInt(); } System.out.println(maxValue(N, C, s, v, w)); }
private static int maxValue(int N, int C, int[] s, int[] v, int[] w) { // 扁平化 List<Integer> worth = new ArrayList<>(); List<Integer> volume = new ArrayList<>(); // 我们希望每件物品都进行扁平化，所以首先遍历所有的物品 for (int i = 0; i < N; i++) { // 获取每件物品的出现次数 int val = s[i]; // 进行扁平化：如果一件物品规定的使用次数为 7 次，我们将其扁平化为三件物品：1*重量&1*价值、2*重量&2*价值、4*重量&4*价值 // 三件物品都不选对应了我们使用该物品 0 次的情况、只选择第一件扁平物品对应使用该物品 1 次的情况、只选择第二件扁平物品对应使用该物品 2 次的情况，只选择第一件和第二件扁平物品对应了使用该物品 3 次的情况 ... for (int k = 1; k <= val; k *= 2) { val -= k; worth.add(w[i] * k); volume.add(v[i] * k); } if (val > 0) { worth.add(w[i] * val); volume.add(v[i] * val); } }
// 0-1 背包问题解决方案 int[] dp = new int[C + 1]; for (int i = 0; i < worth.size(); i++) { for (int j = C; j >= volume.get(i); j--) { dp[j] = Math.max(dp[j], dp[j - volume.get(i)] + worth.get(i)); } } return dp[C]; }}
复制代码
这时候算法的时间复杂度为 $O(∑log S[i] * C)$。
这时候的 $∑log S[i]$ 为 S 数组里的物品数量进行二进制展开后的总和。
相比于原本为 $O(∑S[i] * C)$ 的时间复杂度要下降不少。
多重背包问题的「单调队列」解法
多重背包问题 III ：题目和「多重背包问题 I」完全一样，只是数据范围从 百级 上升到 万级 。
在「多重背包问题 I」的朴素解法中，我们是先循环物品（范围 0 ~ N - 1），再循环容量（范围 0 ~ C），再循环每件物品可以选择的次数（范围 0 ~ s[i] ）。
import java.util.*;class Main { public static void main(String[] arg) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; int[] s = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); s[i] = sc.nextInt(); } System.out.println(maxValue(N, C, s, v, w)); }
private static int maxValue(int N, int C, int[] s, int[] v, int[] w) { int[] dp = new int[C + 1]; int[] g = new int[C + 1]; // 辅助队列，记录的是上一次的结果 int[] q = new int[C + 1]; // 主队列，记录的是本次的结果
// 枚举物品 for (int i = 0; i < N; i++) { int vi = v[i]; int wi = w[i]; int si = s[i]; // 将上次算的结果存入辅助数组中 g = dp.clone();
// 枚举余数 for (int j = 0; j < vi; j++) { int hh = 0, tt = -1; // 枚举同一余数情况下，有多少种方案。例如余数为 1 的情况下有：1、vi + 1、2 * vi + 1、3 * vi + 1 ... for (int k = j; k <= C; k+=vi) { dp[k] = g[k]; if (hh <= tt && q[hh] < k - si * vi) hh++; if (hh <= tt) dp[k] = Math.max(dp[k], g[q[hh]] + (k - q[hh]) / vi * wi); while (hh <= tt && g[q[tt]] - (q[tt] - j) / vi * wi <= g[k] - (k - j) / vi * wi) tt--; q[++tt] = k; } } } return dp[C]; }}
复制代码
在多重背包的单调队列解法中，除了用于保存答案的 dp 数组以外，我们要需要两个数组 g 和 q 来充当队列。
先枚举所有的物品，在枚举每件物品的时候取出该物品的体积 vi 、价值 wi 和数量 si；同时将 dp 中的内容复制到队列中（就是将前 i - 1 件物品的计算结果从 dp 复制到队列 g 中）
再枚举每个余数，由于当前物品的体积为 vi，因此余数范围在 [0, vi) 左闭右开区间中；同时在计算每个余数的时候重新初始化两个队列（重置队列头下标 hh 和队列尾下标 tt）
再枚举在某个余数的情况下，有多少方案。例如余数为 1 的情况下有：1、vi + 1、2 * vi + 1、3 * vi + 1 ...
1. dp[k] = g[k]; ：首先将上一次的计算结果存入
2. if (hh <= tt && q[hh] < k - si * vi) hh++; ：将队列头部中不合法的元素移除（将 hh 往前移动）
3. if (hh <= tt) dp[k] = Math.max(dp[k], g[q[hh]] + (k - q[hh]) / vi * wi); ：更新 dp[k]，在原来的答案 dp[k] 和 g[q[hh]] + (k - q[hh]) / vi * wi) 之间取最大值，g[q[hh]] + (k - q[hh]) / vi * wi) 其实就是 dp[j - k v] + k w 的展开式，此时有 q[hh] = j - k * v, j = k
4. while (hh <= tt && g[q[tt]] - (q[tt] - j) / vi * wi <= g[k] - (k - j) / vi * wi) tt--; ：维护队列的单调性
5. q[++tt] = k; ：将 k 入队
混合背包问题
混合背包问题 ：其实就是 0-1 背包、完全背包 和 多重背包 的混合版本。
仍然是给定物品数量 N 和背包容量 C。第 i 件物品的体积是 v[i]，价值是 w[i]，可用数量为 s[i]。
当 s[i] 为 -1 代表是该物品只能用一次；当 s[i] 为 0 代表该物品可以使用无限次；当 s[i] 为任意正整数则代表可用 s[i] 次。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
s[i] 的几种状态就对应了 0-1 背包、完全背包 和 多重背包。
我们知道 0-1 背包问题将当前容量 j 从大到小遍历，而完全背包则是将当前容量 j 从小到大遍历，多重背包可以用过「二进制优化」彻底转移成 0-1 背包问题。
它们的状态转移方程都一样，所以我们只需要根据第 i 个物品是 0-1 背包物品还是完全背包问题，选择不同的遍历顺序即可。
import java.util.*;class Main { public static void main(String[] arg) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; int[] s = new int[N]; for (int i = 0; i < N; i++){ v[i] = sc.nextInt(); w[i] = sc.nextInt(); s[i] = sc.nextInt(); } System.out.println(maxValue(N, C, s, v, w)); }
private static int maxValue(int N, int C, int[] s, int[] v, int[] w) { List<Integer> worth = new ArrayList<>(); List<Integer> volume = new ArrayList<>(); for (int i = 0; i < N; i++) { int type = s[i]; if (type > 0) { // 将多重背包问题转换为 0-1 背包问题 for (int k = 1; k <= type; k *= 2) { type -= k; worth.add(w[i] * k); volume.add(v[i] * k); } if (type > 0) { worth.add(w[i] * type); volume.add(v[i] * type); } } else if (type == -1) { worth.add(w[i]); volume.add(v[i]); } else { // 对于完全背包，将 worth 翻转，用作标记 worth.add(-w[i]); volume.add(v[i]); } }
int[] dp = new int[C + 1]; for (int i = 0; i < worth.size(); i++) { int wor = worth.get(i); int vol = volume.get(i); if (wor < 0) { // 完全背包问题 for (int j = vol; j <= C; j++) { dp[j] = Math.max(dp[j], dp[j - vol] - wor); // 将 worth 重新翻转为正整数 } } else { // “原 0-1 背包物品” 或 “由多重背包转移过来的 0-1 背包问题” for (int j = C; j >= vol; j--) { dp[j] = Math.max(dp[j], dp[j - vol] + wor); } } } return dp[C]; }}
复制代码
就这样我们解决了这个混合背包问题。
先将一个多重背包问题根据「二进制优化」的思路，转化为 0-1 背包问题，然后根据物品是属于 0-1 背包 还是 完全背包 决定容量 j 是从大到小还是从小到大进行推算。
换句话说就是根据物品的类型不同，选择不同的转移方式。
多维背包问题
多维背包问题 ：有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次，第 i 件物品的体积是 v[i]，重量是 m[i]，价值是 w[i]。
求解将哪些物品装入背包可使这些物品的重量和体积总和都不超过限制，且价值总和最大。
上面所说的背包问题都只有“体积”这么一个限制条件，而多维背包问题是指物品同时会有多个限制条件，如该例的重量。
但由于每件物品都只能用一次，其实本质还是一个 0-1 背包问题，只是做法在从前基础上（维度表示体积）增加一维（一个维度代表体积，一个维度代表重量）。
相应的（完整）状态转移方程也很好得出：
f[i][C][M]=max(f[i−1][C][M],f[i−1][C−v[i]][M−m[i]]+w[i])
和之前几个背包问题一样，我们可以将 i （代表物品下标的）这一维消掉，因为我们在决策第 i 个物品的时候只依赖于决策第 i - 1 个物品时的结果，配合着从大到小的处理顺序，我们可以只用“一个单位”的维度装下所有我们需要的结果。
在多维背包问题中“一个单位”就是指只包含限制条件的多维 dp，对应到该题就是 dp[C][M]。
import java.util.*;class Main { public static void main(String[] arg) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); int M = sc.nextInt(); int[] v = new int[N]; int[] m = new int[N]; int[] w = new int[N]; for (int i = 0; i < N; i++) { v[i] = sc.nextInt(); m[i] = sc.nextInt(); w[i] = sc.nextInt(); } System.out.println(maxValue(N, V, M, v, m, w)); }
private static int maxValue(int N, int C, int M, int[] v, int[] m, int[] w) { int[][] dp = new int[C + 1][M + 1]; for (int i = 0; i < N; i++) { for (int j = C; j >= v[i]; j--) { for (int k = M; k >= m[i]; k--) { dp[j][k] = Math.max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]); } } } return dp[C][M]; }}
复制代码
二维背包问题是通过增加维度来解决，其他多维背包问题也是同理，都是通过增加维度来解决问题，转移方程不变。事实上，当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加维度以满足新的限制是一种比较通用的方法。
分组背包问题
分组背包问题 ：有 N 组物品和一个容量为 C 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 v[i][j]，价值是 w[i][j]，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
import java.util.*;class Main { public static void main(String[] arg) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); int[] S = new int[N]; int[][] v = new int[N][]; int[][] w = new int[N][]; for (int i = 0; i < N; i++) { int si = sc.nextInt(); S[i] = si; int[] vol = new int[si]; int[] wor = new int[si]; for (int j = 0; j < si; j++) { vol[j] = sc.nextInt(); wor[j] = sc.nextInt(); } v[i] = vol; w[i] = wor; } System.out.println(maxValue(N, V, S, v, w)); }
private static int maxValue(int N, int C, int[] S, int[][] v, int[][] w) { int[] dp = new int[C + 1]; for (int i = 0; i < N; i++) { int[] vol = v[i]; int[] wor = w[i]; int si = S[i]; for (int j = C; j >= 0; j--) { for (int k = 0; k < si; k++) { if (j >= vol[k]) { dp[j] = Math.max(dp[j], dp[j - vol[k]] + wor[k]); } } } } return dp[C]; }}
复制代码
背包问题具体方案数
背包问题求方案数 ：有 N 件物品和一个容量是 C 的背包。
每件物品只能使用一次。
第 i 件物品的体积是 v[i]，价值是 w[i]。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最优选法的方案数。
import java.util.*;class Main { private static final int mod = 1000000007; public static void main(String[] arg) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); int[] v = new int[N]; int[] w = new int[N]; for (int i = 0; i < N; i++) { v[i] = sc.nextInt(); w[i] = sc.nextInt(); } System.out.println(combineCount(N, V, v, w)); }
private static int combineCount(int N, int C, int[] v, int[] w) { // 构建一个 dp 数组，除了第一位为 0，其他位均为 Integer.MIN_VALUE int[] dp = new int[C + 1]; for (int i = 1; i <= C; i++) dp[i] = Integer.MIN_VALUE;
// 再构建一个 g 数组来存储不同容量下的方案数，除了第一位为 1，其他位均为 0 int[] g = new int[C + 1]; g[0] = 1;
for (int i = 0; i < N; i++) { for (int j = C; j >= v[i]; j--) { int val = Math.max(dp[j], dp[j - v[i]] + w[i]); int cnt = 0;
// val 有可能等于 dp[j]，有可能等于 dp[j - v[i]] + w[i]，也有可能都等于 // 如果 val 为 dp[j]，增加 g[j] if (val == dp[j]) cnt += g[j]; // 如果 val 为 dp[j - v[i]] + w[i]，增加 g[j - v[i]] if (val == dp[j - v[i]] + w[i]) cnt += g[j - v[i]]; // 采用更为“高效”的取余方法 if (cnt >= mod) cnt -= mod;
dp[j] = val; g[j] = cnt; } }
int max = 0; for (int i = 0; i <= C; i++) max = Math.max(max, dp[i]); int ans = 0; for (int i = 0; i <= C; i++) { if (dp[i] == max) { ans += g[i]; if (ans >= mod) ans -= mod; } } return ans; }}
复制代码
这个解法有点啰嗦，但这是个更为通用的解法。
不仅可以求最大容量时的方案数，还能求具体某个容量时的方案是，只需要将最后一个循环中所使用的 max 变量修改为目标容量即可。
背包问题具体方案
背包问题求具体方案 ：有 N 件物品和一个容量是 C 的背包。
每件物品只能使用一次。
第 i 件物品的体积是 v[i]，价值是 w[i]。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。求字典序最小的具体方案。
这里的字典序是指：所选物品的编号所构成的序列 1 ... N 。
由于求背包最大价值时的状态 f[i][j] 定义是：考虑前 i 件物品，容量不超过体积 j 的情况下，得到的最大价值。
状态转移方程是 f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w) ，也就是每一个 f[i][j] 都是由对于第 i 件物品的决策而来：选择第 i 件物品或不选择第 i 件物品。
所以可以将 f[i][j] 和 f[i - 1][j] 、f[i - 1][j - v] + w 进行比较，得出 f[i][j] 是由选择还是不选择第 i 件物品转移过来的。
总结一下，就是根据以下逻辑来“反推”具体方案数：
仅满足 f[i][j] == f[i - 1][j] ：f[i][j] 是由不选择第 i 件物品转移过来，物品 i 不在具体方案数里面
仅满足 f[i][j] == f[i - 1][j - v] + w ：f[i][j] 是由选择第 i 件物品转移过来的，物品 i 在具体方案里面
满足 f[i][j] == f[i - 1][j] == f[i - 1][j - v] + w ：f[i][j] 即可以由选择第 i 件物品转移过来，也可以由不选择第 i 件物品转移过来，由于求的是最小方案数，所以能选择靠前的物品的话，尽量选择。当物品编号从小到大顺序遍历时，可选可不选的情况，则选。物品 i 在具体方案里面
为了方便我们能够按物品编号从小到大顺序 遍历得到具体方案数，最好让 f[1][C] 为最大价值，也就是在计算最大价值的时候我们应该按照从 N ... 1 的顺序进行递推。
具体代码如下：
import java.util.*;class Main { static int N = 1010; static int C = 1010; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int c = sc.nextInt(); int[] wi = new int[N]; int[] vi = new int[N]; for (int i = 1; i <= n; i++) { vi[i] = sc.nextInt(); wi[i] = sc.nextInt(); } int[][] f = new int[N][C]; // 从 N ... 1 的顺序进行考虑 for (int i = n; i >= 1; i--) { for (int j = 0; j <= c; j++) { f[i][j] = f[i + 1][j]; if (j - vi[i] >= 0) { f[i][j] = Math.max(f[i][j], f[i + 1][j - vi[i]] + wi[i]); } } }
// System.out.print(f[1][c]); // 最大价值
int t = c; // 从 1 ... N 反推具体方案 for (int i = 1; i <= n; i++) { int v = vi[i]; int w = wi[i]; if (t >= v && f[i][t] == f[i + 1][t - v] + w) { System.out.print(i + " "); t -= v; } } }}
复制代码
有依赖的背包问题
有依赖的背包问题 ：有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
如果选择物品 5，则必须选择物品 1 和 2。这是因为 2 是 5 的父节点，1 是 2 的父节点。
每件物品的编号是 i，体积是 v[i]，价值是 w[i]，依赖的父节点编号是 p[i]。
物品的下标范围是 1 … N。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
该题本质是一道树形 dp 题，可以通过递归求解。同时每颗子树又能视为一个分组背包来求解：
import java.util.*;class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] V = new int[N]; int[] W = new int[N]; int[] P = new int[N]; for (int i = 0; i < N; i++) { V[i] = sc.nextInt(); W[i] = sc.nextInt(); P[i] = sc.nextInt(); } int ans = maxValue(N, C, V, W, P); System.out.println(ans); }
private static int maxValue(int N, int C, int[] V, int[] W, int[] P) { // dp[x][v]：选择以 x 为子树的物品，在容量不超过 v 时所获得的最大价值 int[][] dp = new int[N][C + 1];
// 建立一个数组，每个下标存放对应 “以该下标为父节点” 的所有子节点（root 节点的编号为 1） // 该数组下标为 0 的存放的是 root 节点，下标为 1 存放的是以 root 节点为父节点的结点 ... List<Integer>[] tree = new List[N + 1]; Arrays.setAll(tree, e -> new ArrayList<Integer>()); int root = -1; for (int i = 0; i < N; i++) { if (P[i] == -1) { root = i; } else { tree[P[i]].add(i); } }
// dfs 求解 dfs(N, C, V, W, dp, root, tree);
// 最终答案是以 root 为子树（代表了 root 本身也是可以被选或不选）、容量不超过 C 的最大价值 return dp[root][C]; }
private static void dfs(int N, int C, int[] V, int[] W, int[][] dp, int root, List<Integer>[] tree) { int vi = V[root]; int wi = W[root]; for (int i = vi; i <= C; i++) { dp[root][i] = wi; } List<Integer> child = tree[root + 1]; // root 的编号为 1 int size = child.size(); for (int i = 0; i < size; i++) { int node = child.get(i); dfs(N, C, V, W, dp, node, tree); for (int j = C; j >= vi; j--) { for (int k = 0; k <= j - vi; k++) { dp[root][j] = Math.max(dp[root][j], dp[root][j - k] + dp[node][k]); } } } } }
复制代码
总结
几乎所有的背包问题，都是先遍历物品，再遍历容量，最后再遍历决策（在遍历决策里可能又是通过循环实现）。
背包问题的本质其实是这么一个模型：我有一些额度（背包容量）用来做决策（选择物品），做决策会伴随着成本和收益，求解在额度以内的最大收益。
所有的背包问题的变种都离不开这个模型。
另外根据不同的状态定义，可以采取不同的初始化的策略：
状态定义为考虑前 i 件物品，体积最多（不超过）为 j 的话：全部初始化为 0，递推过程保证体积大于等于 0
状态定义为考虑前 i 件物品，体积恰好为 j 的话：只有 f[0][0] 初始为 0，其他为正无穷，递推过程保证体积大于等于 0
状态定义为考虑前 i 件物品，体积至少为 j 的话：只有 f[0][0] 初始为 0，其他为正无穷，递推过程对体积没有要求，但负数的体积可以用体积为 0 来替代
评论