hdu 4501三重包问题

好好理解一下背包问题

从01包入手内层的循环是为了以后求解记录数据因为只有一个取舍问题所以只需要一层循环就可以

这里有三个背包钱积分以及免费物品

那么就需要三重循环

#include<stdio.h>
#include<string.h>
#define N 105
int dp[N][N][10];
int Max(int x,int y)
{
if(x>y)
return x;
else
return y;
}
int main()
{
int n,v1,v2,t;
int a[N],b[N],c[N];
int i,j,k,l;
while(scanf("%d%d%d%d",&n,&v1,&v2,&t)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
{
for(j=v1;j>=0;j--)
for(k=v2;k>=0;k--)
for(l=t;l>=0;l--)
{
int temp=0;
if(l>0)///这里得注意控制条件不能写在循环里面放在里面会减少其他包的数据
temp=Max(temp,dp[j][k][l-1]+c[i]);
if(k>=b[i])
temp=Max(temp,dp[j][k-b[i]][l]+c[i]);
if(j>=a[i])
temp=Max(temp,dp[j-a[i]][k][l]+c[i]);
dp[j][k][l]=Max(dp[j][k][l],temp);
}
}
printf("%d\n",dp[v1][v2][t]);
}
return 0;
}

巴特西

hdu 4501三重包问题

最新文章

热门文章