【题目来源】
AcWing：2. 01背包问题 - 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
【输出样例】
8
【算法标签】
《AcWing 2 01背包问题》 #背包问题# #DP#
【代码详解】
// 朴素解法
#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]; // 输入第i件物品的重量和价值}// 动态规划填表// i: 考虑前i件物品// j: 当前背包可用容量for (int i = 1; i <= n; i++) // 遍历每件物品{for (int j = 0; j <= m; j++) // 遍历所有可能的背包容量{// 不选第i件物品的情况f[i][j] = f[i - 1][j];// 如果能选第i件物品（当前容量j ≥ 物品i的重量v[i]）if (j >= v[i]){// 选择第i件物品的情况// 价值 = 不选第i件物品时的价值 + 第i件物品的价值// 容量 = 当前容量j - 物品i的重量v[i]f[i][j] = max(f[i][j], f[i - 1][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]; // 输入第i件物品的重量和价值}// 动态规划填表// 外层循环：遍历每件物品for (int i = 1; i <= n; i++){// 内层循环：反向遍历背包容量// 必须从大到小遍历，确保每个物品只被选一次for (int j = m; j >= v[i]; 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
8