开始 2023-01-12 15:45:00

20230112D班兔年赛

结束 2023-01-28 17:30:00
Contest is over.
当前 2024-11-28 11:37:12

《采药》题解

这条题目是一条很简单的01背包的题目,因为每一种草药只有一株。 定义dp_{i,j}为容积为j的背包装前i个物品能获得的最大价值。对于每个物品,只有取和不取两种状态。

#include<cstdio>
#include<algorithm>
using namespace std;
int t,m,p[101],v[101],dp[101][1001];
int main(){
	scanf("%d %d",&t,&m);
	for(int i=1;i<=m;i++) scanf("%d %d",&p[i],&v[i]);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=t;j++){
			dp[i][j]=dp[i-1][j];//不取
			if(j>=p[i])dp[i][j]=max(dp[i][j],dp[i-1][j-p[i]]+v[i]);//取
		}
	} 
	printf("%d",dp[m][t]);
	return 0;
}

201902tjc  •  1年前

对不起,我写错了,应该是

定义dp_i,j为j的时间前i个草药能采到的最大价值


201902tjc  •  1年前

比赛已结束。