P1048 [NOIP2005 普及组] 采药 题解

原题链接

题目大意：

采药，每种药只有一株，每株有它的价值和采它所需的时间，现时间有限，请你输出在有限时间内能获得的价值最大是多少。

分析：

1.这是一个典型的01背包问题（DP）

01背包问题的典型特征：

有一个限定容量的背包（对应本题中的时间），有物品（每种只有一个）（对应本题中的药株），物品有体积（对应本题中采集所需的时间）与价值，问最大能获得多少价值？

二维DP：

设第i个物品的重量为w[i],价值为v[i],背包总容量为W

设dp数组，dp[i][j]为只能放前i个物品且背包容量为j的情况下所能获得的最大价值

转移：假设当前已经处理好了前i-1个物品的所有状态，那么对于第i个物品

有 不放入背包：背包剩余容量不变，背包中物体的总价值不变，所一这种情况的最大价值为

dp[i-1][j];

放入背包：背包剩余容量减小w[i],背包中物品的总价值会增大v[i],所以这种情况的最大价值为

dp[i-1][j-w[i]]+v[i].

由此得状态转移方程:

        dp[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])

此题数据规模小，用二维dp可以过

AC代码：

#include<iostream>
#include<cstdio>
using namespace std;
int v[1005],w[1005],n,m,dp[105][1005];
int main(){
	cin>>m>>n;//m代表t,n代表m(题中的)
	for(int i=1;i<=n;i++){
		scanf("%d%d",&v[i],&w[i]);
	} 
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=v[i]){//还有时间才行
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

但是二维dp通常会爆MLE，所以我们要优化空间复杂度

dp[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])

(设第i个物品的重量为w[i],价值为v[i],背包总容量为W

设dp数组，dp[i][j]为只能放前i个物品且背包容量为j的情况下所能获得的最大价值)

考虑使用滚动数组优化

由于对dp[i]有影响的只有dp[i-1],可以去掉第一维，直接用dp[i]来表示处理到当前物品时背包容量为

i的最大价值，得

        f[j]=max(f[j],f[j-w[i]]+v[i])

新代码：

#include<iostream>
using namespace std;
int t,m;
struct node{
	int ti,w;
}ra[102];
int dp[1005];
int main(){
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>ra[i].ti>>ra[i].w;
	}
	int add=0;
	for(int i=1;i<=m;i++){
		for(int j=t;j>=0;j--){
			if(j>=ra[i].ti)
			dp[j]=max(dp[j],dp[j-ra[i].ti]+ra[i].w);
		}
	}
	cout<<dp[t];
	return 0;
}