【题目来源】
AcWing：4. 多重背包问题 I - AcWing题库
【题目描述】
有 \(N\) 种物品和一个容量是 \(V\) 的背包。
第 \(i\) 种物品最多有 \(s_i\) 件，每件体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
【输入】
第一行两个整数，\(N,V\)，用空格隔开，分别表示物品种数和背包容积。
接下来有 \(N\) 行，每行三个整数 \(v_i,w_i,s_i\)，用空格隔开，分别表示第 \(i\) 种物品的体积、价值和数量。
【输出】
输出一个整数，表示最大价值。
【输入样例】
4 5
1 2 3
2 4 1
3 4 3
4 5 2
【输出样例】
10
【解题思路】
【算法标签】
《AcWing 4 多重背包问题I》 #背包问题# #DP#
【代码详解】
// 引入所有标准库头文件，方便使用各种标准库功能
#include <bits/stdc++.h>// 使用标准命名空间，避免每次使用标准库函数时都需要加 std:: 前缀
using namespace std;// 定义常量
const int N = 110; // 定义物品种类和背包容量的最大值为110// 定义全局变量
int n, m; // n: 物品的种类数量，m: 背包的容量
int v[N], w[N], s[N]; // v[N]: 存储每个物品的体积，w[N]: 存储每个物品的价值，s[N]: 存储每个物品的数量
int f[N][N]; // f[i][j]: 表示前i种物品，背包容量为j时的最大价值// 主函数，程序的入口点
int main()
{// 读取物品种类数量n和背包容量mcin >> n >> m; // n: 物品种类数量，m: 背包容量// 循环读取每个物品的体积v[i]、价值w[i]和数量s[i]，并存储到对应的数组中for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i]; // v[i]: 第i种物品的体积，w[i]: 第i种物品的价值，s[i]: 第i种物品的数量// =============================// 动态规划部分：计算前i种物品，背包容量为j时的最大价值// 使用三维动态规划思想，通过三层循环实现// =============================// 外层循环：遍历所有物品种类，从第1种到第n种for (int i = 1; i <= n; i++) {// 中层循环：遍历所有可能的背包容量，从0到mfor (int j = 0; j <= m; j++) {// 内层循环：遍历当前物品i的所有可能选取数量，从0到s[i]for (int k = 0; k <= s[i]; k++) {// 检查当前选取数量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;
}
【运行结果】
4 5
1 2 3
2 4 1
3 4 3
4 5 2
10