题解：P1048 [NOIP2005 普及组] 采药

· · 题解

思路：

参考了 OI Wiki。

背包 DP 模版题。

首先定义一个 dp 数组，其中 dp_{i,j} 表示第 i 个物品在背包容量为 j 时的最大价值。

考虑转移。

枚举每一个物品在背包容量剩余 j 时可以得到的最大价值。

如果现在枚举的剩余容量 j 小于选择这个物品需要的容量，那么 dp_{i,j} 的最大值就是 dp_{i-1,j}。

否则有两种情况，选和不选。
对于选的情况，背包的剩余容量会减小这个物品需要的容量，价值会增加这个物品的价值，故此情况下的价值为 dp_{i-1,j-uset_i}+price_i；对于不选的情况，这个物品不会放进背包，所以和剩余容量不够的情况是一样的是 dp_{i-1,j}。

在此处再解释下 dp_{i-1,j-uset_i}+price_i，这个时候需要选择第 i 件物品，因为第 i 件物品需要的空间是 uset_i 枚举的背包容量等于 j，所以只剩下 j-uset_i 空间就是留给前 i-1 件物品，然后 dp_{i-1,j-uset_i} 是第 i-1 件物品，背包容量剩余 j-uset_i 时的最大值，而现在我们又选择了第 i 件物品，所以现在的价值是 dp_{i-1,j-uset_i}+price_i。

所以可以得出转移方程：

对于剩余容量大于等于选择这个物品需要的容量时

dp_{i,j}=\max(dp_{i-1,j-uset_i}+price_i,dp_{i-1,j})

否则

dp_{i,j}=dp_{i-1,j}

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int m,n,t;
int dp[1050][1050];
int uset[105],price[105];
int main(){
    cin>>t>>m;
    for(int i=1;i<=m;i++)
        cin>>uset[i]>>price[i];
    for(int i=1;i<=m;i++)
        for(int j=0;j<=t;j++){
            if(j>=uset[i])
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-uset[i]]+price[i]);
            else
                dp[i][j]=dp[i-1][j];
        }
    cout<<dp[m][t];
    return 0;
}