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;}