【题目来源】
AcWing：3. 完全背包问题 - AcWing题库
【题目描述】
有 \(N\) 种物品和一个容量是 \(V\) 的背包，每种物品都有无限件可用。
第 \(i\) 种物品的体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
【输入】
第一行两个整数，\(N,V\)，用空格隔开，分别表示物品种数和背包容积。
接下来有 \(N\) 行，每行两个整数 \(v_i,w_i\)，用空格隔开，分别表示第 \(i\) 种物品的体积和价值。
【输出】
输出一个整数，表示最大价值。
【输入样例】
4 5
1 2
2 4
3 4
4 5
【输出样例】
10
【算法标签】
《AcWing 3 完全背包问题》 #背包问题# #DP#
【代码详解】
/*
1. 01背包: f[i][j] = max(f[i-1][j], f[i-1][j-v]+w);
2. 完全背包: f[i][j] = max(f[i-1][j], f[i][j-v]+w);
*/
// 朴素版本
#include <bits/stdc++.h>
using namespace std;const int N = 1005; // 最大物品数和背包容量
int n, m; // n: 物品数量, m: 背包容量
int v[N], w[N]; // v[i]: 第i件物品的重量, w[i]: 第i件物品的价值
int f[N][N]; // f[i][j]: 前i件物品，总重量不超过j的最大价值int main()
{// 输入物品数量和背包容量cin >> n >> m;// 输入每件物品的重量和价值// 注意：物品编号从1开始，方便理解for (int i = 1; i <= n; i++){cin >> v[i] >> w[i];}// 动态规划填表// 外层循环：遍历每件物品for (int i = 1; i <= n; i++){// 内层循环：遍历背包容量for (int j = 1; j <= m; j++){// 1. 不选第i件物品f[i][j] = f[i - 1][j];// 2. 如果可以选第i件物品（当前容量j ≥ 物品i的重量v[i]）if (j >= v[i]){// 选择第i件物品// 注意：这里是f[i][j-v[i]]，不是f[i-1][j-v[i]]// 因为完全背包中，每件物品可以选无限次f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);}}}// 输出结果：前n件物品，背包容量为m时的最大价值cout << f[n][m] << endl;return 0;
}
// 一维数组版
#include <bits/stdc++.h>
using namespace std;const int N = 1005; // 最大物品数和背包容量
int n, m; // n: 物品数量, m: 背包容量
int v[N], w[N]; // v[i]: 第i件物品的重量, w[i]: 第i件物品的价值
int f[N]; // f[j]: 容量为j时的最大价值（优化为一维数组）int main()
{// 输入物品数量和背包容量cin >> n >> m;// 输入每件物品的重量和价值// 注意：物品编号从1开始，方便理解for (int i = 1; i <= n; i++){cin >> v[i] >> w[i];}// 动态规划填表// 外层循环：遍历每件物品for (int i = 1; i <= n; i++){// 内层循环：正向遍历背包容量// 必须从小到大遍历，允许每个物品被选多次for (int j = v[i]; j <= m; j++){// 状态转移方程：// 1. 不选第i件物品：f[j]保持不变// 2. 选第i件物品：f[j - v[i]] + w[i]f[j] = max(f[j], f[j - v[i]] + w[i]);}}// 输出结果：容量为m时的最大价值cout << f[m] << endl;return 0;
}
【运行结果】
4 5
1 2
2 4
3 4
4 5
10