疯狂的背包问题(13) - 分组背包

题意

$N$ 组物品，背包容量 $V$ 。每组有若干物品，同一组内最多选一个。求最大总价值。

思路

一句话本质：01 背包是每个物品可选/不选，分组背包是每组选 0 或 1 个。需要保留上一组的状态 previous，对当前组每个物品从 previous 转移，防止同组内多选。

先看暴力：

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
38import sys


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    V = next(it)
    groups = []
    for _ in range(N):
        s = next(it)
        group = []
        for __ in range(s):
            v = next(it)
            w = next(it)
            group.append((v, w))
        groups.append(group)

    ans = 0

    def dfs(gid: int, cur_vol: int, cur_val: int) -> None:
        nonlocal ans
        if cur_vol > V:
            return
        if gid == len(groups):
            ans = max(ans, cur_val)
            return
        dfs(gid + 1, cur_vol, cur_val)
        for v, w in groups[gid]:
            if cur_vol + v <= V:
                dfs(gid + 1, cur_vol + v, cur_val + w)

    dfs(0, 0, 0)
    print(ans)


if __name__ == '__main__':
    solve()

暴力 DFS 每组的决策：不选，或选组内某个物品（若容量够）。当 $N=100$ 、每组最多 $100$ 个物品时，分支因子约 101，搜索树爆炸。

分组背包和 01 背包的区别在哪？

01 背包中，每个物品独立，可以选或不选——每轮循环处理一个物品，倒序遍历容量即可，不会混淆不同物品的影响。

但分组背包的约束是一组内只能选一个。组内的多个物品是互斥的：选了 A 就不能选 B。如果像普通 01 背包一样逐个物品放进去，就可能在同组内选了多个——因为后处理的物品会看到先处理的物品的贡献。

怎么能保证同组最多选一个？

分组背包的关键思路：把一组看作一个整体决策单元。处理第 $i$ 组时，先用 previous = dp 保存上一组结束后的状态。然后对当前组内的每个物品，都从 previous 里转移，而不是从当前组的 dp 转移。

具体来说，对当前组内每个物品 $(v, w)$ ：

dp[j] = \max(dp[j],\ previous[j - v] + w)

这里 $j$ 倒序枚举（因为同一物品只选一次）。关键点是所有物品统一从 previous 转移——这样就算组内有多个物品，它们看到的都是"上一组结束"的同一份状态，不会互相看到对方选了之后的贡献，从而保证整个组最多选一个。

为什么不选也是合法决策？

初始化 dp = previous（容量不变、不选任何物品），然后在 $j$ 倒序过程中，每个物品可以选择是否替换到这个容量上。最终 dp[j] 取的是"不选"和"选某物品"中的 $\max$ 。

代码

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#include <bits/stdc++.h>
using namespace std;

struct Item {
    int weight, value;
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int group_count, capacity;
    cin >> group_count >> capacity;
    // dp[c] 表示容量为 c 时的最大价值。
    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_old[c - w] 转移，避免同组内互相影响。
                dp[c] = max(dp[c], previous[c - item.weight] + item.value);
            }
        }
    }
    cout << dp[capacity] << '\n';
    return 0;
}

复杂度

时间 $O(N \times V \times \bar{S})$ ，其中 $\bar{S}$ 是每组平均物品数：每个物品都要遍历容量。空间 $O(V)$ ，只需当前 dp 和一份 previous 副本。数据范围 $N, V, S_i \le 100$ ，总操作约 $10^6$ 。

总结

分组背包的"一组选一个"约束，本质上是对转移来源加了一层隔离——所有物品从同一份旧状态出发。这是一个通用思想：遇到"互斥选择"时，用一份 frozen 的旧状态作为统一参考，防止同类选项之间互相影响。

疯狂的背包问题(13) - 分组背包

目录

题意

思路

代码

复杂度

总结