【题目描述】

一个旅行者有一个最多能装 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

【题目分析】

1. 0-1背包问题，用动态规划思路。

2. 在限重m的情况下求最大价值。

1. 定义状态：

• 定义 dp[j] 为当前背包容量为 j 时可以获得的最大总价值。

• 我们需要一个数组 dp 来保存每个容量下的最大价值，初始时所有值都设为0，因为当背包容量为0时，能放入的价值自然也为0。

2. 状态转移方程：

• 每次考虑第 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] 是不放入它的总价值。取二者的最大值就是我们要更新的新状态。

3. 更新顺序：

• 为了避免在单次迭代中多次使用同一物品，必须从背包容量 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;  }

(adsbygoogle = window.adsbygoogle || []).push({});