多重背包
Problem Description
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），
要求：
输入方式：a1 a2 a3 a4 a5 a6
（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）
输出方式：N
（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
Output
输出N，N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。
SampleOutput
3
Hint:表示可以称出1g，2g，3g三种不同的重量。
#include <cstdio>
#include <cstring>
#define max(x,y) x>y? x:y;
int dp[1005];
int vis[1005];
int main(){
int A[6] = {1,2,3,5,10,20};
int N[6] ;
int sum=0;
for(int i=0;i<6;++i){
scanf("%d",&N[i]);
sum+=N[i]*A[i];
}
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
int count = 0;
for(int i=0;i<6;++i){
for(int j=0;j<N[i];++j){
for(int k=sum;k>=A[i];--k){
dp[k] = max(dp[k-A[i]]+A[i],dp[k]);
if(vis[dp[k]]==0){
count++;
vis[dp[k]]=1;
}
}
}
}
printf("%d\n",count);
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
