【题目来源】
AcWing：9. 分组背包问题 - AcWing题库
【题目描述】
有 \(N\) 组物品和一个容量是 \(V\) 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 \(v_{i,j}\)，价值是 \(w_{i,j}\)，其中 \(i\) 是组号，\(j\) 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
【输入】
第一行有两个整数 \(N,V\)，用空格隔开，分别表示物品组数和背包容量。
接下来有 \(N\) 组数据：
- 每组数据第一行有一个整数 \(S_i\)，表示第 \(i\) 个物品组的物品数量；
- 每组数据接下来有 \(S_i\) 行，每行有两个整数 \(v_{i,j},w_{i,j}\)，用空格隔开，分别表示第 \(i\) 个物品组的第 \(j\) 个物品的体积和价值；
【输出】
输出一个整数，表示最大价值。
【输入样例】
3 5
2
1 2
2 4
1
3 4
1
4 5
【输出样例】
8
【解题思路】
【算法标签】
《AcWing 9 分组背包问题》 #背包问题# #DP#
【代码详解】
// 引入所有标准库头文件，方便使用各种标准库功能
#include <bits/stdc++.h>// 使用标准命名空间，避免每次使用标准库函数时都需要加 std:: 前缀
using namespace std;// 定义常量
const int N = 110; // 定义物品最大分组数量为110// 定义全局变量
int f[N][N]; // f[i][j]: 表示只从前i组物品中选，当前总体积不超过j时的最大价值
int v[N][N], w[N][N]; // v[i][j]: 第i组第j个物品的体积，w[i][j]: 第i组第j个物品的价值
int s[N]; // s[i]: 第i组物品的个数
int n, m; // n: 物品组数，m: 背包容量// 主函数，程序的入口点
int main()
{// 读取物品组数n和背包容量mcin >> n >> m; // n: 物品组数，m: 背包容量// =============================// 输入部分：读取每组物品的信息// =============================// 外层循环：遍历所有物品组，从第1组到第n组for (int i = 1; i <= n; i++) // 第i组{// 读取第i组物品的个数cin >> s[i]; // s[i]: 第i组物品的个数// 内层循环：遍历第i组中的每个物品，从第1个到第s[i]个for (int j = 1; j <= s[i]; j++)// 读取第i组第j个物品的体积v[i][j]和价值w[i][j]cin >> v[i][j] >> w[i][j]; // v[i][j]: 第i组第j个物品的体积，w[i][j]: 第i组第j个物品的价值}// =============================// 动态规划部分：计算只从前i组物品中选，总体积不超过j时的最大价值// 类似于0/1背包问题，但针对每组物品进行选择// =============================// 外层循环：遍历所有物品组，从第1组到第n组for (int i = 1; i <= n; i++) // 类似0/1背包{// 中层循环：遍历所有可能的背包容量，从0到mfor (int j = 0; j <= m; j++) {// 内层循环：遍历当前组i中的每个物品，从第0个到第s[i]个（不选到选s[i]个）for (int k = 0; k <= s[i]; k++) {// 检查当前选择第i组第k个物品是否使得总体积不超过当前背包容量jif (j >= v[i][k]) {// 更新当前状态f[i][j]为选择或不选择第i组第k个物品时的最大价值// f[i][j] = max(f[i][j], f[i-1][j - v[i][k]] + w[i][k])// 解释：// f[i][j] 表示只从前i组物品中选，总体积不超过j时的最大价值// f[i-1][j - v[i][k]] 表示只从前i-1组物品中选，总体积不超过j - v[i][k]时的最大价值（即未选择第i组第k个物品时的状态）// w[i][k] 表示选择第i组第k个物品时的价值// 通过选择或不选择第i组第k个物品，取两者中的最大值来更新f[i][j]f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);}}}}// =============================// 输出结果：在背包容量为m时，选择所有n组物品的最大价值// =============================// 输出f[n][m]，即只从前n组物品中选，总体积不超过m时的最大价值cout << f[n][m] << endl;// 程序正常结束，返回0return 0;
}
【运行结果】
3 5
2
1 2
2 4
1
3 4
1
4 5
8