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

GitHub跳转原题关系图返回列表

每组最多选一个物品：保留上一组状态previous，对当前组每个物品从previous转移，避免组内互窜。

OJ: luogu

题目 ID: U661995

难度:普及+/提高-

标签:动态规划背包分组背包

创建: 2026-08-08 23:13

更新: 2026-10-07 12:15

前置题目
roj 3141数字组合B 的分组背包把 A 教的「倒序枚举让物品至多选一次、取旧值」当作组内物品层转移规则，再叠加 previous 冻结上一组状态来实现组内互斥luogu P1734最大约数和B 的分组背包把 A 教的「容量倒序遍历让物品至多选一次」当作物品层转移规则，再叠加 previous 冻结上一组状态；倒序是 B 每件物品由未选中态转移所必需的步骤，但仅此还不够隔离同组互斥，组内隔离是 B 新增的台阶。
后置题目
luogu P2015二叉苹果树B 的 main.cpp 完整复用了 A 教的「冻结旧状态、组内候选项统一从旧状态转移」这一步：先 new_dp[t]=dp[u][t]（不选该组），再用 new_dp[used+take+1]=max(..., dp[u][used]+dp[v][take]+w) 从冻结的 dp[u] 转移，只是把 A 的一维容量组背包扩成「每个儿子子树为一组、take 为组内选项」的树上分组背包，并额外叠加父边必留的 +1 与后序合并流程。luogu P2014[CTSC1997] 选课B 的 main.cpp:33-41 复用了 A 的分组背包步骤——把每个孩子子树当成一组物品、按组分配名额转移 dp[u][j-k]+dp[v][k]，A 教的“一组当整体决策单元、组间用独立状态隔离”正是这一步的基础；B 在其上叠加虚拟根把森林变树、树形 DP 与子树状态定义。luogu P5322[BJOI2019] 排兵布阵A 教的分组背包用 previous = dp 冻结上一组状态、组内物品统一从 previous 转移以保证组内最多选一个；B 把每座城堡的台阶方案当成一组的互斥选项，main.cpp 先 ndp = dp 再对每个台阶用 dp[money - cost] 转移，正是同一份旧状态隔离手法，额外只加了排序合并阈值台阶的建模。luogu P5365英雄联盟B 的 main.cpp 第 35-45 行先把 dp 备份成 ndp，再对每个英雄枚举 x≥2 从旧状态 dp[cost] 乘出 ndp[nc]，正是 A 教的『分组背包用 previous 备份冻结上一组状态、组内选项统一从旧状态转移』这一步，用来防止同一英雄重复买皮肤；B 只在其上叠加乘法收益与截断到 M，难度 普及+/提高- → 普及+/提高，方向正确。

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

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

思路

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

先看暴力：

py
import 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=100N=100、每组最多 100100 个物品时，分支因子约 101，搜索树爆炸。

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

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

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

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

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

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

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

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

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

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

代码

cpp
#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×V×Sˉ)O(N \times V \times \bar{S})，其中 Sˉ\bar{S} 是每组平均物品数：每个物品都要遍历容量。空间 O(V)O(V)，只需当前 dp 和一份 previous 副本。数据范围 N,V,Si≤100N, V, S_i \le 100，总操作约 10610^6。

总结

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