A85 采药 题解

题目意思

你有一个容量为 $T$ 的背包，而你面前有 $M$ 个物品，每个物品都有它的价值和重量。
现在你要让这个背包里装的物品总价值最高，那么这个总价值是多少？

DP 讲解

这道题是 DP（动态规划）的模版题，所以我会详细讲解 DP 的解题过程，会背包 DP 的人可以直接拉到下面看代码。

---

对于这类总价值最高的问题，我们可以使用 背包 DP 来解决。

首先我们需要将输入存起来。
使用 $v_i$ 表示一个物品的价值，$w_i$ 表示一个物品的重量。

接下来维护一个 $dp$ 数组。
$dp_i$ 表示的是：当背包容量为 $i$ 时，最多可以装的总价值。

然后，我们需要枚举每件物品，然后考虑：拿或不拿，谁的价值更高？

for(int i=1;i<=m;i++)

接下来，我们需要枚举背包容量。
需要注意的是，枚举背包容量时，枚举范围是 T 到 w[i] 。
这是为什么呢？

我们设想一下：如果正序枚举，会发生什么？
此时，前面枚举的结果会污染到后面的计算，误以为新的计算结果是上一轮的计算结果，从而导致结果偏差。

for(int i=1;i<=n;i++){
    for(int j=t;j>=w[i];j--){
        // 注意是 j-- 不是 j++
    }
}

现在到了最核心的部分：怎么考虑拿不拿谁的价值更高？

我们可以使用 max() 函数计算，一边是不拿的结果，一边是拿的结果。
左边的值肯定就是 $dp_j$ 了。
而右边的，就是 dp[ j-w[i] ] + v[i] 了。
仔细想一下这个式子，它的意思就是：

背包容量 -= 这个物品的重量
价值 += 这个物品的价值

所以，核心部分就出来了：

for(int i=1;i<=n;i++){
    for(int j=t;j>=w[i];j--){
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}

需要注意的地方

• $dp$ 数组的大小不是 $M$（物品数量），而是 $T$（背包容量）。
• 内层循环的边界是 $w_i$ ，防止越界

AC Code

#include <iostream>
using namespace std;
const int N=102;
int w[N],v[N],dp[1002]; // 注意 dp 数组要根据背包容量开大小
int main(){
    int t,m; cin>>t>>m;
    for(int i=1;i<=m;i++) cin>>w[i]>>v[i]; // 分别代表重量和价值

    for(int i=1;i<=m;i++){ // 枚举每一个物品
        for(int j=t;j>=w[i];j--){ // 枚举背包容量
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]); // 状态转移方程
        }
    }

    cout<<dp[t]; // 背包容量为 T 时的价值就是答案
    return 0;
}