通天之分组背包

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

把物品按组分类，每组最多选一件，外层遍历组、内层倒序枚举容量、最内层遍历组内物品做 01 转移，保证同组互斥。

OJ: luogu

题目 ID: P1757

难度:普及-

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

创建: 2026-08-09 12:00

更新: 2026-08-09 12:00

目录

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

    题意

    有 n 件物品，每件物品有重量 a_i、价值 b_i、所属组别 c_i。同组物品相互冲突，即每组最多选一件。背包容量为 m，求最大总价值。

    思路

    一句话本质：在 01 背包的基础上加一层"组"的约束——外层按组遍历，每组内做一次 01 背包，通过容量倒序和组内物品共用同一轮 dp 实现互斥。

    先看最直接的暴力枚举，帮助理解题意：

    py
    import sys

data = sys.stdin.buffer.read().split()
m = int(data[0])
n = int(data[1])

items_by_group = {}
idx = 2
for _ in range(n):
    w = int(data[idx]); idx += 1
    v = int(data[idx]); idx += 1
    g = int(data[idx]); idx += 1
    items_by_group.setdefault(g, []).append((w, v))

groups = list(items_by_group.values())
k = len(groups)

ans = 0

def dfs(g_idx, cur_w, cur_v):
    global ans
    if cur_w > m:
        return
    if cur_v > ans:
        ans = cur_v
    if g_idx == k:
        return
    dfs(g_idx + 1, cur_w, cur_v)
    for w, v in groups[g_idx]:
        dfs(g_idx + 1, cur_w + w, cur_v + v)

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

    brute.py 对每组要么不选，要么选组内某一件物品。递归遍历所有组，记录当前重量和价值，超容量则剪枝。复杂度很高，只适合小数据验证。

    分组背包和 01 背包的本质区别是什么？

    01 背包中每个物品独立选/不选；分组背包中物品被分到多个组，同组物品不能同时选。如果直接把所有物品当 01 背包处理，就丢失了"同组互斥"的约束。

    怎么保证同组物品互斥？

    把"组"引入 DP 的外层循环。对每一组，在所有组内物品上共用同一轮容量枚举。因为容量倒序保证了一个物品不会被重复选，而同一轮内不同物品共用相同的 dp 快照，相互之间自然不能同时生效——这就实现了互斥。

    转移怎么写，三层循环的顺序有讲究吗？

    设 dp[j] 表示容量不超过 j 时的最大总价值。

    对第 g 组（组内有物品 (w, v)）：

    • 外层：容量 j 从 m 到 0 倒序
    • 内层：遍历组内每个物品 (w, v)，若 j ≥ w 则 dp[j] = max(dp[j], dp[j - w] + v)

    容量循环必须在组内物品循环的外层。如果反过来（先物品后容量），那就退化成普通 01 背包，丢失了组内互斥的约束。

    状态表

    状态 含义
    dp[j] 处理完若干组后，容量不超过 j 的最大总价值

    代码

    cpp
    /**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-08 23:13
 * update_at: 2026-08-08 23:13
 * 分组背包
 */
#include <bits/stdc++.h>
using namespace std;

const int maxv = 1005;
int m, n;
vector<pair<int,int>> grp[105];
int dp[maxv];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> m >> n;
    int mxg = 0;
    for (int i = 1; i <= n; ++i) {
        int w, v, g;
        cin >> w >> v >> g;
        grp[g].push_back({w, v});
        mxg = max(mxg, g);
    }
    for (int g = 1; g <= mxg; ++g) {
        if (grp[g].empty()) continue;
        for (int j = m; j >= 0; --j) {
            for (auto &[w, v] : grp[g])
                if (j >= w)
                    dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    cout << dp[m] << "\n";
    return 0;
}

    复杂度

    • 时间复杂度：O(k · m)，其中 k 为物品总数，m 为背包容量
    • 空间复杂度：O(m)

    总结

    分组背包的关键只有一条：容量倒序循环在组内物品循环的外面。这个顺序保证了同组物品不会在同一个 dp 值上叠加。以后看到"物品分若干类，每类最多选一个"时，直接套分组背包模板即可。