【动态规划/背包问题】分组背包问题
前言
今天是我们讲解「动态规划专题」中的「背包问题」的第十二篇。
今天将会学习「分组背包」问题。
另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解（每隔几天更新一篇，确保大家消化）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~
分组背包
给定
个物品组，和容量为
的背包。
第
个物品组共有
件物品，其中第
组的第
件物品的成本为
，价值为
。
每组有若干个物品，同一组内的物品最多只能选一个。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
示例：
输入：N = 2, C = 9, S = [2, 3], v = [[1,2,-1],[1,2,3]], w = [[2,4,-1],[1,3,6]]
输出：10
提示：
基本分析
从题面看，这似乎是一种全新的背包问题。
但其仍然是一种通过「枚举物品 - 枚举容量 - 枚举决策」来解决的组合优化问题。
经过之前 三种传统背包问题 的学习。
我们可以很轻松给出状态定义：定义
为考虑前
个物品组，背包容量不超过
的最大价值。
不失一般性的考虑
如何计算。
由于每组有若干个物品，且每组「最多」选择一件物品。
即对于第
组而言，可决策的方案如下：
- 不选择该组的任何物品：
- 选该组的第一件物品：
- 选该组的第二件物品：
...
- 选该组的最后一件件物品：
显然最终的
应该是从所有方案里取
：
代码：
class Solution {
public int maxValue(int N, int C, int[] S, int[][] v, int[][] w) {
int[][] dp = new int[N + 1][C + 1];
for (int i = 1; i <= N; i++) {
int[] vi = v[i - 1];
int[] wi = w[i - 1];
int si = S[i - 1];
for (int j = 1; j <= C; j++) {
dp[i][j] = dp[i - 1][j];
for (int k = 0; k < si; k++) {
if (j >= vi[k]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - vi[k]] + wi[k]);
}
}
}
}
return dp[N][C];
}
}
- 时间复杂度：
- 空间复杂度：
空间优化
滚动数组
根据状态转移方程，不难发现
只依赖于
，且
。
即明确只依赖上一物品组的决策结果。
因此，我们可以使用 最开始 就学过的「滚动数组」的方式，十分机械的将
的空间优化到
。
代码：
class Solution {
public int maxValue(int N, int C, int[] S, int[][] v, int[][] w) {
int[][] dp = new int[2][C + 1];
for (int i = 1; i <= N; i++) {
int[] vi = v[i - 1];
int[] wi = w[i - 1];
int si = S[i - 1];
for (int j = 1; j <= C; j++) {
int a = i & 1, b = (i - 1) & 1;
dp[a][j] = dp[b][j];
for (int k = 0; k < si; k++) {
if (j >= vi[k]) {
dp[a][j] = Math.max(dp[a][j], dp[b][j - vi[k]] + wi[k]);
}
}
}
}
return dp[N & 1][C];
}
}
- 时间复杂度：
- 空间复杂度：
一维空间优化
进一步，我们可以用「01 背包」类似的思路，进行一维空间优化：
- 取消物品维度；
- 将容量维度的遍历顺序修改为「从大到小」（确保所依赖的值不会被覆盖）。
代码：
class Solution {
public int maxValue(int N, int C, int[] S, int[][] v, int[][] w) {
int[] dp = new int[C + 1];
for (int i = 1; i <= N; i++) {
int[] vi = v[i - 1];
int[] wi = w[i - 1];
int si = S[i - 1];
for (int j = C; j >= 0; j--) {
for (int k = 0; k < si; k++) {
if (j >= vi[k]) {
dp[j] = Math.max(dp[j], dp[j - vi[k]] + wi[k]);
}
}
}
}
return dp[C];
}
}
- 时间复杂度：
- 空间复杂度：
总结
经过「一维空间」优化发现，分组背包问题的空间优化无法降低运算量。
因此我们只能采用「枚举物品 - 枚举容量 - 枚举决策」的朴素思路来求解。
但对于「组内」物品而言，由于最多只能选一件物品，因此对于成本相同的多件物品，我们应当只保留价值最大的物品，从而让总的物品数量变少。
但这样的预处理优化，也只是常数级别的优化。
事实上，分组背包问题的应用不仅仅只有「每组最多选择一件物品」的形式，还有诸如「每组必须选择一件物品」的形式。
明天我们会用一道 LeetCode 练习题来复习分组背包问题。
背包问题（目录）
腾讯云开发者
