题目信息
- 平台:牛客
- 题目:【模板】分组背包
- 难度:中等
- 题目链接:【模板】分组背包_牛客题霸_牛客网
题目描述
给定
第
- 重量
; - 价值
; - 所属组别
。
请在不超过背包承重
输入描述
第一行输入两个整数
接下来
输出描述
输出一个整数,表示在约束条件下可以获得的最大价值。
初步思路
- 这是背包问题的经典变形——分组背包。与 01 背包唯一的区别是:物品的选取单位从「单件」变成了「组」,每组至多选一件。
- 每组内的决策是「不选」或「选组内某一件」,天然满足互斥,不需要额外去重。
- 数据范围
, 级别的 DP 完全可行;但 可达 ,价值和会爆 int,必须用 64 位整数。
关键结论:容量倒序枚举才能保证组内互斥
状态定义为:
对每一组,枚举容量
三层循环的顺序固定为:
为什么必须倒序? 倒序枚举容量时,
- 同一组内的物品不会互相叠加(读到的都是旧值);
- 每组自然只贡献至多一件物品。
如果正序枚举,
算法流程
- 读入物品,按组编号
收纳到 101 个桶中; 的物品永远选不了,直接丢弃。 - 初始化
(容量允许不装满,全零即可)。 - 对每一组:容量
从 倒序到 ,枚举组内物品,若 则执行转移。 - 输出
。
样例:
物品为
- 组 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;
}import sys
from collections import defaultdict
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
n = int(data[idx]); idx += 1
m = int(data[idx]); idx += 1
groups = defaultdict(list)
for _ in range(n):
w = int(data[idx]); v = int(data[idx + 1]); k = int(data[idx + 2])
idx += 3
if w <= m: # 单件超重,直接丢弃
groups[k].append((w, v))
dp = [0] * (m + 1)
for grp in groups.values():
for j in range(m, 0, -1): # 倒序:保证每组至多选一件
for w, v in grp:
if w <= j and dp[j - w] + v > dp[j]:
dp[j] = dp[j - w] + v
sys.stdout.write(str(dp[m]) + '\n')
if __name__ == '__main__':
solve()import java.io.*;
import java.util.*;
public class Main {
@SuppressWarnings("unchecked")
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
List<long[]>[] g = new ArrayList[101];
for (int i = 0; i <= 100; i++) g[i] = new ArrayList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int w = Integer.parseInt(st.nextToken());
long v = Long.parseLong(st.nextToken());
int k = Integer.parseInt(st.nextToken());
if (w <= m) g[k].add(new long[]{w, v});
}
long[] dp = new long[m + 1];
for (int k = 0; k <= 100; k++) {
for (int j = m; j >= 1; j--) { // 倒序:保证每组至多选一件
for (long[] item : g[k]) {
int w = (int) item[0];
long v = item[1];
if (w <= j) dp[j] = Math.max(dp[j], dp[j - w] + v);
}
}
}
System.out.println(dp[m]);
}
}package main
import (
"bufio"
"fmt"
"os"
)
type item struct {
w int
v int64
}
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n, m int
fmt.Fscan(in, &n, &m)
groups := make([][]item, 101)
for i := 0; i < n; i++ {
var w, k int
var v int64
fmt.Fscan(in, &w, &v, &k)
if w <= m { // 单件超重,直接丢弃
groups[k] = append(groups[k], item{w, v})
}
}
dp := make([]int64, m+1)
for _, grp := range groups {
for j := m; j >= 1; j-- { // 倒序:保证每组至多选一件
for _, it := range grp {
if it.w <= j && dp[j-it.w]+it.v > dp[j] {
dp[j] = dp[j-it.w] + it.v
}
}
}
}
fmt.Fprintln(out, dp[m])
}use std::io::{self, Read, Write};
fn main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
let mut tokens = input.split_whitespace();
let n: usize = tokens.next().unwrap().parse().unwrap();
let m: usize = tokens.next().unwrap().parse().unwrap();
let mut groups: Vec<Vec<(usize, i64)>> = vec![Vec::new(); 101];
for _ in 0..n {
let w: usize = tokens.next().unwrap().parse().unwrap();
let v: i64 = tokens.next().unwrap().parse().unwrap();
let k: usize = tokens.next().unwrap().parse().unwrap();
if w <= m { // 单件超重,直接丢弃
groups[k].push((w, v));
}
}
let mut dp = vec![0i64; m + 1];
for grp in &groups {
for j in (1..=m).rev() { // 倒序:保证每组至多选一件
for &(w, v) in grp {
if w <= j && dp[j - w] + v > dp[j] {
dp[j] = dp[j - w] + v;
}
}
}
}
let mut out = io::stdout().lock();
writeln!(out, "{}", dp[m]).unwrap();
}易错点
- 循环顺序不能乱:必须是「组 → 容量倒序 → 组内物品」。把「组内物品」提到容量外层,或容量正序枚举,都会破坏组内互斥。
- **倒序的终止条件判断的是
而不是 **:误写成 M > 0是恒真条件,会导致死循环和数组越界。 - **转移前先判断
**:否则访问 dp[j-w]下标为负。 - 价值要开 64 位整数:
,2000 件物品的价值和远超 int上限。 - 预处理剪枝:
的物品直接不读入分组,避免无效转移。 - 变量名大小写:C++ 区分大小写,
dp(m+1)与dp(M+1)是两个不同的标识符。
可改进点
- 若物品按组乱序给出且组编号范围未知,可以先用
unordered_map动态建组,避免开固定 101 的桶。 - 组数很大而每组物品很少时,可以只对非空组建索引,跳过早期的空组循环。
- 若题目改为「每组至少选一件」或「每组选若干件」,只需改初始值或改转移枚举方式,框架不变。
总结
分组背包 = 01 背包的「选择单位升级」。核心要点一句话:
三层循环「组 → 容量倒序 → 组内物品」,靠倒序枚举容量保证每组至多选一件。
掌握这个模板后,多重背包(二进制拆分转 01 背包)、依赖背包等问题都可以在这个框架上扩展。