文章
4
粉丝
67
获赞
5
访问
18.2k
这是道多重背包的问题,因此用多重背包的经典代码即可解决
# 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;
}
登录后发布评论
暂无评论,来抢沙发