HDOJ 3732 Ahui Writes Word (多重背包)
http://acm.hdu.edu.cn/showproblem.php?pid=3732
这是一道很坑爹的题呀！！！一打眼看看以为是简单的01背包，然后就华丽的超时了……
后来才发现被迷惑了！这是一道多重背包的问题。
这道题足以给做惯了经典多重背包，已经出定势思维的我们敲响警钟了！
这题一个特点：物品个数很大，背包的体积很大，但是物品的价值和花费都很小！
题意：有N个单词，总复杂度为C，已知每个单词的价值和复杂度，求不超过C可获得的最大价值。
思路：现统计有多少种“单词”，然后通过多重背包解决问题~
#include<stdio.h>#include<string.h>int bag[11111],v[111111],w[111111],vc[11][11];int main(){int n,c;while(scanf("%d%d",&n,&c)==2){char ip[11];int i,j,k=0,a,b;memset(vc,0,sizeof(vc));for(i=1;i<=n;i++){scanf("%s%d%d",ip,&a,&b);vc[a][b]++;}for(i=1;i<=10;i++)//统计种类数for(j=1;j<=10;j++)if(vc[i][j]){int tmp=1;while(vc[i][j]>tmp){v[k]=tmp*i;w[k++]=tmp*j;vc[i][j]-=tmp;tmp<<=1;}v[k]=vc[i][j]*i;w[k++]=vc[i][j]*j;}memset(bag,0,sizeof(bag));for(i=1;i<k;i++)for(j=c;j>=w[i];j--)if(bag[j]<bag[j-w[i]]+v[i])bag[j]=bag[j-w[i]]+v[i];printf("%d\n",bag[c]);}return 0;}