【题目来源】
洛谷：AT_dp_e Knapsack 2 - 洛谷
【题目描述】
\(N\) 个物品被编号为 \(1, 2, \ldots, N\)。对于 \(1 \leq i \leq N\)，物品 \(i\) 的重量是 \(w _ i\)，价值是 \(v _ i\)。
太郎君决定从 \(N\) 个物品中选择一些放入背包中带回家。背包的容量为 \(W\)，带回的物品的总重量不能超过 \(W\)。
请计算太郎君能带回的物品的最大总价值。
【输入】
输入以以下格式从标准输入中提供：
\(N\) \(W\)
\(w _ 1\) \(v _ 1\)
\(w _ 2\) \(v _ 2\)
\(\ldots\)
\(w _ N\) \(v _ N\)
【输出】
输出太郎君能带回的物品的最大总价值。
【输入样例】
3 8
3 30
4 50
5 60
【输出样例】
90
【算法标签】
《洛谷 AT_dp_e Knapsack 2》 #动态规划DP# #背包DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100005; // 数组最大容量
int n, m; // n: 物品数量，m: 背包容量限制
int dp[N], w[105], v[105], tot; // dp: 动态规划数组，w: 物品重量，v: 物品价值，tot: 总价值int main()
{cin >> n >> m; // 读入物品数量和背包容量限制// 读入每个物品的重量和价值，并计算总价值for (int i = 1; i <= n; i++){cin >> w[i] >> v[i];tot += v[i];}// 初始化dp数组为无穷大memset(dp, 0x3f, sizeof(dp));dp[0] = 0; // 价值为0时，重量为0// 01背包动态规划for (int i = 1; i <= n; i++){for (int j = tot; j >= v[i]; j--){// 状态转移：要么不选当前物品，要么选当前物品dp[j] = min(dp[j], dp[j - v[i]] + w[i]);}}// 从最高价值向低遍历，找到第一个重量不超过m的最大价值for (int i = tot; i >= 0; i--){if (dp[i] <= m){cout << i << endl; // 输出最大价值return 0;}}return 0;
}
【运行结果】
3 8
3 30
4 50
5 60
90