题目信息


题目描述

给定 件物品与一只最大可承重为 的背包。所有物品被划分为 个组别(组编号 ),同一组中的物品互斥:在最终方案中,每组至多选取一件物品。

第 件物品具有如下属性:

  • 重量 ;
  • 价值 ;
  • 所属组别 。

请在不超过背包承重 的前提下,选择若干物品使得总价值最大。

输入描述

第一行输入两个整数 —— 物品数量与背包容量。

接下来 行,第 行输入三个整数 ,描述第 件物品的重量、价值与所属组别。

输出描述

输出一个整数,表示在约束条件下可以获得的最大价值。


初步思路

  1. 这是背包问题的经典变形——分组背包。与 01 背包唯一的区别是:物品的选取单位从「单件」变成了「组」,每组至多选一件。
  2. 每组内的决策是「不选」或「选组内某一件」,天然满足互斥,不需要额外去重。
  3. 数据范围 , 级别的 DP 完全可行;但 可达 ,价值和会爆 int,必须用 64 位整数。

关键结论:容量倒序枚举才能保证组内互斥

状态定义为:

容量为时,处理完当前所有组能获得的最大价值

对每一组,枚举容量 ,再枚举组内每件物品 :

三层循环的顺序固定为:

组容量(从倒序)组内物品

为什么必须倒序? 倒序枚举容量时, 保存的是上一组处理完的旧状态,因此:

  • 同一组内的物品不会互相叠加(读到的都是旧值);
  • 每组自然只贡献至多一件物品。

如果正序枚举, 可能已被本组其他物品更新过,相当于同组选了多件,就退化成了完全背包,答案错误。


算法流程

  1. 读入物品,按组编号 收纳到 101 个桶中; 的物品永远选不了,直接丢弃。
  2. 初始化 (容量允许不装满,全零即可)。
  3. 对每一组:容量 从 倒序到 ,枚举组内物品,若 则执行转移。
  4. 输出 。

样例:

物品为 、、。

  • 组 2 的物品重量 ,预处理时被丢弃;
  • 处理组 1: 时选价值 的物品,;另一件价值 不会更优;
  • 组 2 为空, 不再变化。

最终输出 ,与期望输出一致。


算法分析

  • 核心:分组背包一维 DP,倒序枚举容量保证组内互斥;
  • 预处理:按组收纳物品,丢弃超重物品;
  • 时间复杂度:,其中 为第 组的物品数,代入数据约 ;
  • 空间复杂度:,一维滚动数组。

代码实现

以下给出 C++、Python、Java、Go、Rust 五种语言的实现,逻辑完全一致。切换上方的标签即可对比。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    // 组编号 1~100,按组收纳物品(重量,价值)
    vector<vector<pair<int, ll>>> g(101);

    for (int i = 0; i < N; ++i) {
        int w, k;
        ll v;
        cin >> w >> v >> k;
        // 单件就超过容量的物品永远选不了,直接丢弃
        if (w <= M) g[k].push_back({w, v});
    }

    vector<ll> dp(M + 1, 0);

    for (auto &grp : g) {
        for (int j = M; j >= 1; --j) {      // 倒序:保证每组至多选一件
            for (auto &[w, v] : grp) {
                if (w <= j) dp[j] = max(dp[j], dp[j - w] + v);
            }
        }
    }

    cout << dp[M] << '\n';

    return 0;
}

易错点

  1. 循环顺序不能乱:必须是「组 → 容量倒序 → 组内物品」。把「组内物品」提到容量外层,或容量正序枚举,都会破坏组内互斥。
  2. **倒序的终止条件判断的是 而不是 **:误写成 M > 0 是恒真条件,会导致死循环和数组越界。
  3. **转移前先判断 **:否则访问 dp[j-w] 下标为负。
  4. 价值要开 64 位整数:,2000 件物品的价值和远超 int 上限。
  5. 预处理剪枝: 的物品直接不读入分组,避免无效转移。
  6. 变量名大小写:C++ 区分大小写,dp(m+1) 与 dp(M+1) 是两个不同的标识符。

可改进点

  • 若物品按组乱序给出且组编号范围未知,可以先用 unordered_map 动态建组,避免开固定 101 的桶。
  • 组数很大而每组物品很少时,可以只对非空组建索引,跳过早期的空组循环。
  • 若题目改为「每组至少选一件」或「每组选若干件」,只需改初始值或改转移枚举方式,框架不变。

总结

分组背包 = 01 背包的「选择单位升级」。核心要点一句话:

三层循环「组 → 容量倒序 → 组内物品」,靠倒序枚举容量保证每组至多选一件。

掌握这个模板后,多重背包(二进制拆分转 01 背包)、依赖背包等问题都可以在这个框架上扩展。