HDU-2191-悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2191

多重背包问题： 思路：直接转换为01背包问题

代码

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

int main(void)
{
int i,j,k,l,n,m;
int q,h,c,t;
int w[2005],v[2005];
int dp[105];
scanf("%d",&t);
while(t--)
{
k=0;
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d%d%d",&q,&h,&c);
for(j=0;j<c;j++)
{
w[k]=q; v[k]=h;
k++;
}
}
for(i=0;i<k;i++)
{
for(j=n;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
printf("%d ",dp[n]);
}
return 0;
}

参数

0MS

308K

729 B

也可以  二进制拆分

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int t,n,m,i,j;
int v[510],c[510],dp[410]; //v,c分别存加个和重量。。。数组开500，
//种类最多20个，二进制拆分最多5组，m最大100
int p,h,num;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(dp,0,sizeof(dp));
int count=0;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&p,&h,&num);
int l=1;
while(num>=l) //二进制拆分就是将物体拆分成几个物体。
//比如把13个相同的物品分成4组(1,2,4,6)，这些物体可以组合成1-13中任何数
{
v[count]=p*l;
c[count++]=h*l;
num-=l;
l<<=1; //相当于l=l<<1;就是l乘2
}
if(num)
{
v[count]=p*num;
c[count++]=h*num;
}
}
for(i=0;i<count;i++)
for(j=n;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
printf("%d ",dp[n]);
}
return 0;
}

我的改进版

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

int main(void)
{
int i,j,k,t,n,m,l;
int q,h,c;
int w[510],v[510],dp[110];
scanf("%d",&t);
while(t--)
{
k=0;
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d%d%d",&q,&h,&c);
l=1;
while(c>=l)
{
w[k]=q*l;
v[k++]=h*l;
c=c-l;
l=l<<1;
}
if(c)
{
w[k]=q*c;
v[k++]=h*c;
}
}
for(i=0;i<k;i++)
{
for(j=n;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
printf("%d ",dp[n]);
}
return 0;
}

参数

0MS

300K

885 B