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

{% link 洛谷文章链接,xyx404,https://www.luogu.com.cn/article/y9l0giqv %}

思路：

#

{% link 参考了 OI Wiki, ,https://oi-wiki.org/dp/knapsack/ %}

背包 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$。

所以可以得出转移方程：

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

否则

代码：

#

#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;
}