我的算法书 - 分组背包

一句话算法

分组背包把物品分成若干组，每组最多选一个；处理一组时，所有转移都必须来自上一组的状态。

问题模型

给定 $g$ 组物品和容量为 $C$ 的背包。第 $i$ 组有若干物品，每个物品有重量和价值。

限制：

每组最多选一个物品；
可以不选某一组；
总重量不超过 $C$ ；
总价值最大。

输入格式常见为：

g C
cnt1
w11 v11
w12 v12
...
cnt2
w21 v21
...

核心直觉

分组背包的关键不是“某个物品选不选”，而是：

当前这一组，到底选哪一个，或者一个都不选。

如果处理第 $i$ 组时直接在同一组内部连续更新，就可能出现“一组里选了多个物品”的错误。

所以每处理一组，要先保存上一组处理完的状态 previous，当前组的所有选择都从 previous 转移：

上一组状态 previous
       |
       +-- 不选当前组
       +-- 选当前组第 1 个物品
       +-- 选当前组第 2 个物品
       +-- ...

状态设计

定义：

dp[i][c]

表示只考虑前 $i$ 组物品，容量为 $c$ 时能得到的最大价值。

边界：

dp[0][c]=0

状态转移

不选第 $i$ 组任何物品：

dp[i][c] = dp[i-1][c]

选第 $i$ 组中的第 $k$ 个物品：

dp[i][c] = dp[i-1][c-w_{i,k}] + v_{i,k}

前提是 $c\ge w_{i,k}$ 。

合并得到：

dp[i][c]=\max\left( dp[i-1][c], \max_{k,\ c\ge w_{i,k}}\{dp[i-1][c-w_{i,k}]+v_{i,k}\} \right)

算法步骤

初始化 dp[c] = 0。
枚举每一组物品。
复制上一组结果：previous = dp。
枚举容量 c = 0..C。
先令 dp[c] = previous[c]，表示当前组不选。
枚举当前组每个物品，如果能放下，就用 previous[c-weight] + value 更新。
所有组处理完后，输出 dp[C]。

算法证明

核心不变量：处理完第 $i$ 组后，dp[c] 等于只使用前 $i$ 组物品、容量不超过 $c$ 的最大价值。

边界正确

没处理任何组时，不选物品，价值为 $0$ 。
分类完整

对第 $i$ 组，合法方案只有两类：不选这一组，或选这一组中的某一个物品。
不选当前组

最优值直接来自前 $i-1$ 组：

$dp[i-1][c]$
选当前组某个物品

假设选第 $k$ 个物品，则剩余容量为 $c-w_{i,k}$ 。由于每组最多选一个，剩余方案只能来自前 $i-1$ 组：

$dp[i-1][c-w_{i,k}]+v_{i,k}$
为什么必须用 previous

如果从当前 dp 转移，当前组前面的物品可能已经更新过 dp，后面的物品再使用它，就会在同一组内选多个物品。

使用 previous 可以保证每一次选择当前组物品时，来源都是“上一组结束后的状态”。

因此转移正确，算法正确。

复杂度分析

设总物品数为 $M$ ，容量为 $C$ 。

时间复杂度： $O(MC)$ 。
空间复杂度： $O(C)$ 。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

        #include <bits/stdc++.h>
using namespace std;

struct Item {
    int weight;
    int value;
};

int main() {
    int group_count, capacity;
    cin >> group_count >> capacity;

    vector<int> dp(capacity + 1, 0);

    for (int group_id = 1; group_id <= group_count; group_id++) {
        int item_count;
        cin >> item_count;

        vector<Item> group(item_count);
        for (int i = 0; i < item_count; i++) {
            cin >> group[i].weight >> group[i].value;
        }

        vector<int> previous = dp;
        for (int c = 0; c <= capacity; c++) {
            dp[c] = previous[c];
            for (const Item &item : group) {
                if (c < item.weight) continue;
                dp[c] = max(dp[c],
                            previous[c - item.weight] + item.value);
            }
        }
    }

    cout << dp[capacity] << "\n";
    return 0;
}

测试用例

输入：

输出：

解释：可以从第 1 组选重量 2、价值 3 的物品，从第 2 组选重量 2、价值 5 的物品，再从第 3 组选重量 4、价值 3 会超出容量。因此最优为第 1 组重量 3 价值 4，第 2 组重量 2 价值 5，总重量 5，总价值 9。

应用分类详解

分组背包的本质是：选择被分成互斥集合，每个集合里最多选一个。只要题目出现“每类最多一个”“每个阶段选择一个方案”“多种互斥升级路径”，就应该考虑分组背包。

一、每组最多选一个

典型模式： 物品天然分组，每组内部互斥。

识别信号： 出现“每组最多选择一个”“每门课程选一个方案”“每个主件只能选一种附件组合”。

核心建模： 组是 DP 的阶段，组内物品是当前阶段的候选决策。

应用场景	经典题目	核心思路
分组背包模板	acwing-9	每组最多选一个物品
课程选择方案	luogu-P2014	每个节点的子方案可转成分组选择

二、互斥方案选择

典型模式： 对同一个对象有多个升级方案，只能采用其中一个。

识别信号： 出现“方案 A/B/C 只能选一个”“同一装备只能强化一次”。

核心建模： 把同一对象的所有方案放入同一组。

应用场景	经典题目	核心思路
装备升级	luogu-P1064	主件和附件组合可视为互斥方案
多方案预算	luogu-P1757	每类物品最多选一件

三、树形和依赖背包的局部合并

典型模式： 在树形结构中，每个子树提供多种可选状态。

识别信号： 出现“依赖关系”“选父才能选子”“树上 DP 合并”。

核心建模： 子节点提供的一组状态在合并时类似分组背包。

应用场景	经典题目	核心思路
树上背包	luogu-P2014	子树状态按容量合并
有依赖的背包	luogu-P1064	附件依赖主件，枚举合法组合

经典例题

1. acwing-9

分组背包模板题。直接套用“枚举组、枚举容量、枚举组内物品”的转移。

2. luogu-P1757

每类物品最多选一件，是分组背包的标准模型。

3. luogu-P1064

金明的预算方案。先把主件及附件组合成若干互斥方案，再做分组背包。

参考

旧版文章：Rbook_ejs_old/book/dynamic_programming/knapsack/grouped_knapsack/index.md
前置：01 背包