解题思路

背包能装最大重量 maxw，有 n 件物品（重量+价值），每件物品只能选一次，问装进背包的价值最大是多少。

这是经典的 01 背包问题。

思路：动态规划。

设 dp[j] 表示背包容量为 j 时能装到的最大价值。

对每个物品 i，有两种选择：

• 不装：dp[j] 保持不变
• 装：dp[j - 物品重量] + 物品价值

取两者更大的：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

为什么容量要从大到小遍历？ 因为每个物品只能选一次。如果从小到大遍历，dp[j - weight[i]] 可能已经被当前物品更新过，就会重复选这个物品（变成无限背包）。从大到小遍历，dp[j - weight[i]] 还是上一轮的值，保证每个物品只选一次。

举例：背包容量 10，物品 (4,5)、(3,4)、(6,9)：

• 选 (4,5) 和 (6,9)，总重 10，总价值 14
• 这就是最优解

参考代码

#include <iostream>
using namespace std;

int main() {
    int maxw, n;
    cin >> maxw >> n;

    int weight[105], value[105];
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    int dp[20005] = {0};  // dp[j] = 容量 j 的最大价值

    for (int i = 1; i <= n; i++) {
        for (int j = maxw; j >= weight[i]; j--) {  // 从大到小
            if (dp[j - weight[i]] + value[i] > dp[j]) {
                dp[j] = dp[j - weight[i]] + value[i];
            }
        }
    }

    cout << dp[maxw] << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N×maxw)，每件物品遍历所有容量
• 空间复杂度：O(maxw)，一维 dp 数组