hdu 2844 Coins - 多重背包
/*问一些硬币能组合到的钱数有多少种？多重背包 容量等于价值的算一种*/#include<stdio.h>#include<string.h>struct node{int w,v,c;}wu[150];int n,m;int dp[101000];void cpack(int c,int ww,int*d,int w) { int j; for(j=c;j<=w;j++) { if((d[j-c]+ww)>d[j]) d[j]=d[j-c]+ww; } } void znpack(int c,int ww,int*d,int w) { int j; for(j=w;j>=c;j--) { if(d[j]<(d[j-c]+ww)) d[j]=d[j-c]+ww; } } void mpack(int c,int ww,int nn,int*d,int w) { if(c*nn>=w) { cpack(c,ww,d,w); return; } int k=1; while(k<nn) { znpack(k*c,k*ww,d,w); nn=nn-k; k=k*2; } znpack(nn*c,nn*ww,d,w); } int main(){int i,ret;while(scanf("%d%d",&n,&m),n+m){ret=0;memset(dp,0,sizeof(dp));for(i=0;i<n;i++){scanf("%d",&wu[i].w);wu[i].v=wu[i].w;}for(i=0;i<n;i++){scanf("%d",&wu[i].c);}for(i=0;i<n;i++){if(wu[i].c)mpack(wu[i].w,wu[i].v,wu[i].c,dp,m);}for(i=1;i<=m;i++){if(dp[i]&&dp[i]!=dp[i-1]) ret++;}printf("%d\n",ret);}return 0;}