什么是分组背包？
分组背包（Group Knapsack） 是 0-1 背包的扩展。在分组背包中，物品被分成若干组，每组内的物品互斥——每组最多只能选择一件物品（或不选）。这是实际生活中常见的一类决策问题。
问题描述
有 n 组物品和一个容量为 W 的背包。第 i 组有 k[i] 件物品，第 i 组的第 j 件物品重量为 w[i][j]，价值为 v[i][j]。每组最多选一件，求最大价值。
动态规划解法
定义 dp[i][w] 表示：考虑前 i 组物品，背包容量为 w 时的最大价值。
状态转移方程：
dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i][j]] + v[i][j])
其中 j 为第 i 组的任一物品核心思想：对于每一组，枚举组内所有物品的选择情况。
C++ 代码实现
#include <iostream>
#include <vector>
using namespace std;
// 分组背包 - 二维 DP
int group_knapsack_2d(const vector<vector<int>>& weight,
const vector<vector<int>>& value, int W) {
int n = weight.size(); // 组数
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
// 首先默认不选这一组的任何物品
dp[i][w] = dp[i-1][w];
// 枚举第 i 组的所有选择
for (int j = 0; j < weight[i-1].size(); j++) {
if (w >= weight[i-1][j]) {
dp[i][w] = max(dp[i][w],
dp[i-1][w - weight[i-1][j]] + value[i-1][j]);
}
}
}
}
return dp[n][W];
}
// 分组背包 - 一维 DP（空间优化）
int group_knapsack_1d(const vector<vector<int>>& weight,
const vector<vector<int>>& value, int W) {
int n = weight.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
// 逆序遍历容量（0-1背包特性，每组最多选一件）
for (int w = W; w >= 0; w--) {
// 枚举第 i 组的所有选择
for (int j = 0; j < weight[i].size(); j++) {
if (w >= weight[i][j]) {
dp[w] = max(dp[w],
dp[w - weight[i][j]] + value[i][j]);
}
}
}
}
return dp[W];
}
// 记录具体的选择方案
struct Choice {
int group_idx;
int item_idx;
};
vector<Choice> group_knapsack_with_choice(const vector<vector<int>>& weight,
const vector<vector<int>>& value, int W) {
int n = weight.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// 填充 DP 表
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
dp[i][w] = dp[i-1][w];
for (int j = 0; j < weight[i-1].size(); j++) {
if (w >= weight[i-1][j]) {
dp[i][w] = max(dp[i][w],
dp[i-1][w - weight[i-1][j]] + value[i-1][j]);
}
}
}
}
// 回溯找出选择
vector<Choice> choices;
int w = W;
for (int i = n; i > 0 && w > 0; i--) {
for (int j = 0; j < weight[i-1].size(); j++) {
if (w >= weight[i-1][j] &&
dp[i][w] == dp[i-1][w - weight[i-1][j]] + value[i-1][j]) {
choices.push_back({i-1, j});
w -= weight[i-1][j];
break; // 找到这一组的选择后退出
}
}
}
return choices;
}
int main() {
// 示例：3组物品
// 第0组：{手机, 平板} - 只能选一个
// 第1组：{耳机, 音箱} - 只能选一个
// 第2组：{键盘, 鼠标} - 只能选一个
vector<vector<int>> weight = {
{2, 3}, // 第0组：重量2或3
{1, 4}, // 第1组：重量1或4
{2, 1} // 第2组：重量2或1
};
vector<vector<int>> value = {
{3000, 4000}, // 第0组：价值3000或4000
{500, 1500}, // 第1组：价值500或1500
{400, 200} // 第2组：价值400或200
};
int W = 5; // 背包容量
cout << "分组背包示例:" << endl;
cout << "背包容量: " << W << endl;
cout << "\n各组物品:" << endl;
for (int i = 0; i < weight.size(); i++) {
cout << "第" << i << "组: ";
for (int j = 0; j < weight[i].size(); j++) {
cout << "[w=" << weight[i][j] << ",v=" << value[i][j] << "] ";
}
cout << endl;
}
cout << "\n最大价值 (二维DP): " << group_knapsack_2d(weight, value, W) << endl;
cout << "最大价值 (一维DP): " << group_knapsack_1d(weight, value, W) << endl;
// 输出选择方案
vector<Choice> choices = group_knapsack_with_choice(weight, value, W);
cout << "\n选择的物品: ";
for (auto& c : choices) {
cout << "(组" << c.group_idx << ", 物品" << c.item_idx
<< ": w=" << weight[c.group_idx][c.item_idx]
<< ", v=" << value[c.group_idx][c.item_idx] << ") ";
}
cout << endl;
return 0;
}复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 二维 DP | O(n × W × m) | O(n × W) |
| 一维 DP | O(n × W × m) | O(W) |
其中 n 是组数，W 是容量，m 是平均每组物品数。
分组背包的典型应用
- 旅行打包：不同类别的物品，每类最多带一件
- 预算分配：不同类型的投资，每类选择一个项目
- 课程安排：不同时段的课程，每时段选一门
- 游戏装备：不同部位的装备，每部位最多穿一件
总结
分组背包是 0-1 背包的自然扩展，核心在于组内互斥的约束。解题时只需在 0-1 背包的基础上，对每一组内的物品进行枚举即可。空间优化技巧与 0-1 背包相同，使用一维数组时需要逆序遍历容量。