【模板】分组背包
时间限制：5 秒
空间限制：512M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
给定n nn件物品与一只最大可承重为M MM的背包。所有物品被划分为k kk个组别（组编号1 ∼ k 1 \sim k1∼k），同一组中的物品互斥：在最终方案中，每组至多选取一件物品。
第i ii件物品具有如下属性：
- 重量w i w_iwi；
- 价值v i v_ivi；
- 所属组别g i ∈ { 1 , 2 , … , k } g_i \in \{1, 2, \dots, k\}gi∈{1,2,…,k}。
请你在不超过背包承重M MM的前提下，选择若干物品使得总价值最大。
输入描述
第一行输入两个整数n , M ( 1 ≤ n , M ≤ 2000 ) n, M\ (1 \le n, M \le 2000)n,M(1≤n,M≤2000)——物品数量与背包容量。
接下来n nn行，第i ii行输入三个整数w i , v i , g i ( 1 ≤ w i , v i ≤ 10 9 , 1 ≤ g i ≤ 100 ) w_i, v_i, g_i\ (1 \le w_i, v_i \le 10^9,\ 1 \le g_i \le 100)wi,vi,gi(1≤wi,vi≤109,1≤gi≤100)，描述第i ii件物品的重量、价值与所属组别。
输出描述
输出一个整数，表示在约束条件下可以获得的最大价值。
示例
示例 1
输入：
3 45 10 10 1 10 5 1 50 400 2输出：
10说明：共有两组：组1 11有两件重量10 1010的物品，价值分别为10 1010与5 55；组2 22有一件重量50 5050的物品，价值400 400400。背包容量仅为45 4545，无法选择组2 22的物品，因此最佳方案为在组1 11中选择价值为10 1010的物品，得到答案10 1010。
数据范围
- 1 ≤ n , M ≤ 2000 1 \le n, M \le 20001≤n,M≤2000
- 1 ≤ w i , v i ≤ 10 9 1 \le w_i, v_i \le 10^91≤wi,vi≤109
- 1 ≤ g i ≤ 100 1 \le g_i \le 1001≤gi≤100
解题思路
本题是分组背包的模板题。给定n nn件物品与容量为M MM的背包，所有物品被划分为k kk个组，同一组内的物品互斥，即每组至多选择一件物品。要求在不超过背包容量的前提下，使所选物品的总价值最大。
1. 问题等价转化
- 分组约束：不同组之间相互独立，可以分别选择；同一组内最多选一件。
- 状态定义：设d p [ j ] dp[j]dp[j]表示背包容量为j jj时能获得的最大价值。初始时d p [ j ] = 0 dp[j]=0dp[j]=0（0 ≤ j ≤ M 0\le j\le M0≤j≤M）。
- 转移思路：依次处理每个组。对于当前组，枚举组内每一件物品，再枚举背包容量j jj，尝试用该物品更新状态。为保证同组至多选一件，更新时必须使用上一组处理完毕后的状态作为参考，而不能使用当前组已经更新过的状态。
2. 算法实现
- 按组归类：读入所有物品，用数组
b[g]存储第g gg组的物品列表（每件物品记录重量与价值）。同时求出最大组编号k kk。 - 逐组 DP：
- 对于每个组，先将当前的
dp数组整体备份为old，表示“只考虑前面组时的最优值”。 - 遍历该组中的每一件物品( w , v ) (w, v)(w,v)，对容量j jj从M MM递减到w ww，执行：
d p [ j ] = max ( d p [ j ] , o l d [ j − w ] + v ) dp[j] = \max\big(dp[j],\ old[j-w] + v\big)dp[j]=max(dp[j],old[j−w]+v) - 注意更新时引用的是备份
old，而不是dp本身。这样即使同一组内有多件物品，每件物品也只会基于“尚未选本组任何物品”的状态进行转移，从而保证每组至多选一件。
- 对于每个组，先将当前的
- 输出答案：最终d p [ M ] dp[M]dp[M]即为最大总价值。
3. 复杂度分析
- 时间复杂度：每个组内物品总数之和为n nn，每件物品需要枚举M MM个容量，总复杂度为O ( n M ) O(nM)O(nM)。n , M ≤ 2000 n,M\le 2000n,M≤2000，运算量约4 × 10 6 4\times 10^64×106，完全可行。
- 空间复杂度：需要存储d p dpdp数组和备份数组
old，以及所有物品信息，空间复杂度为O ( n + M ) O(n + M)O(n+M)，远低于512 512512MB 限制。
总结
分组背包的核心在于“每组至多选一件”的约束。通过先备份上一组的状态，再用备份状态更新当前组，可以有效避免同一组内重复选择的问题。该方法将二维分组背包压缩为一维数组，配合倒序枚举容量，实现简洁且高效，是处理分组背包问题的标准做法。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;llf(ll x){ll r=1;while(x--)r<<=1;returnr;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m,w,v,g,k=1;cin>>n>>m;vector<vector<ll>>a(n);for(ll i=0;i<n;i++){cin>>w>>v>>g;a[i]={w,v,g};k=max(k,g);}vector<vector<pll>>b(k);for(autoi:a){b[i[2]-1].emplace_back(i[0],i[1]);}vector<ll>c(m+1,0);for(autoi:b){autoo=c;for(autol:i){for(ll j=m;j-l.first>=0;j--)c[j]=max(c[j],o[j-l.first]+l.second);}}cout<<c[m]<<endl;return0;}