【题解—动态规划】背包问题1
【题目描述】
一个旅行者有一个最多能装 m 公斤物品的背包，现在有 n 件物品，它们的重量分别是 w1,w2,…,wn, 它们的价值分别为 c1,c2,…cn 。若每种物品只有一件，求旅行者能获得的最大总价值。
【输入】
第一行：两个整数 m （背包容量， m ≤ 200 ）和 n （物品数量， n ≤ 30 ）；
第二 行到第n+1 行：每行两个整数 wi,ci, 表示每个物品的重量和价值。
【输出】
一个数据，表示最大总价值。
【输入样例】
10 4 2 1 3 3 4 5 7 9
【输出样例】
12
【题目分析】
0-1背包问题，用动态规划思路。
在限重m的情况下求最大价值。
定义状态：
定义
dp[j]为当前背包容量为j时可以获得的最大总价值。我们需要一个数组
dp来保存每个容量下的最大价值，初始时所有值都设为0，因为当背包容量为0时，能放入的价值自然也为0。状态转移方程：
每次考虑第
i件物品，它的重量和价值分别为weights[i]和values[i]。如果我们决定将这个物品放入背包，并且当前背包的剩余容量足够（即
j >= weights[i]），那么可以得到新的状态： dp[j] = max(dp[j], dp[j - weights[i]] + values[i])这里
dp[j - weights[i]] + values[i]是将第i件物品放入背包后的总价值，而dp[j]是不放入它的总价值。取二者的最大值就是我们要更新的新状态。更新顺序：
为了避免在单次迭代中多次使用同一物品，必须从背包容量
m向下遍历到weights[i]（即j--的方向）。如果从前往后更新，会导致当前物品的状态被多个引用覆盖。
核心代码：
// 动态规划处理
for (int i = 0; i < n; i++) {
for (int j = m; j >= weights[i]; j--) {
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}外层循环 (
for (int i = 0; i < n; i++))：遍历所有物品。如果有
n个物品，循环此步骤n次。内层循环 (
for (int j = m; j >= weights[i]; j--))：从背包的最大容量
m开始倒序遍历到weights[i]。这样只会影响当前物品和之前物品的组合，而不会影响未来物品的计算。状态更新：
dp[j]代表当前容量j的最大价值，通过与将当前物品放入背包后的新计算值进行比较，选取较大的那个作为新的最大价值。
【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int m, n;
cin >> m >> n; // 读取背包容量 m 和物品数量 n
int weights[30]; // 存放物品重量，大小为最大数量 n
int values[30]; // 存放物品价值，大小为最大数量 n
int dp[201] = {0}; // dp 数组初始化，大小为最大容量 m + 1，初始值为 0
// 读取每个物品的重量和价值
for (int i = 0; i < n; i++) {
cin >> weights[i] >> values[i];
}
// 动态规划处理
for (int i = 0; i < n; i++) {
for (int j = m; j >= weights[i]; j--) {
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}
// 输出最大总价值
cout << dp[m] << endl;
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。