【题目描述】

【输入】

【输出】

【输入样例】

10 4
2 1
3 3
4 5
7 9

【输出样例】

max=12

【题目分析】

1. 输入部分：

• 首先读取两个整数，m 为背包的最大容量，n 为物品的数量。

• 接着，通过循环读取每个物品的信息，包括其重量 Wi 和价值 Ci。

2. 动态规划数组：

• 创建一个长度为 m + 1 的数组 dp，用于存储在各个可能的背包容量下获得的最大价值。

3. 状态转移处理：

• 外层循环遍历所有的物品（从 0 到 n-1）。

• 内层循环从当前物品的重量开始迭代到背包的最大容量 m。这是因为，对于无限数量的物品，可以多次选择同一物品，所以这里的内层循环的起始位置应该是 weights[i]。

• 在每一步更新 dp[j] 时，计算不选择和选择当前物品所能得到的最大价值，并选择较大值进行更新。

4. 输出结果：

• 最后，打印出在背包最大容量 m 下的最大总价值。

  
  

【参考代码】

#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 = weights[i]; j <= m; j++) { // 从 weights[i] 开始更新
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    // 输出最大总价值
    cout << "max=" << dp[m] << endl;

    return 0;
}