文章

4

粉丝

67

获赞

5

访问

18.2k

头像
魔兽争霸3之冰封王座
P1112
发布于2022年6月10日 19:06
阅读数 4.6k

这是道多重背包的问题,因此用多重背包的经典代码即可解决

# include<stdio.h>
# include<string.h>
struct node
{
	int v;
	int w;
}g[105];

int Max(int a,int b)
{
	return a>b?a:b;
}

int main()
{
	int nCase,nVal;
	int i,j;
	int dp[2005];
	while((scanf("%d %d",&nCase,&nVal))!=EOF)
	{
		for(i=0;i<nCase;i++)
		scanf("%d %d",&g[i].v,&g[i].w);
		memset(dp,0,sizeof(dp));
		for(i=0;i<nCase;i++) //多重背包的经典代码
		for(j=g[i].v;j<=nVal;j++)
		dp[j]=Max(dp[j-g[i].v]+g[i].w,dp[j]);
		printf("%d\n",dp[nVal]);
	}
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发