1 #include<stdio.h> 2 #include<string.h> 3 int a[102],c[102],dp[100005]; 4 int max(int a,int b) 5 { 6     return a>b?a:b; 7 } 8 void CompletePack(int v,int w,int m) //完全背包 9 {10      for(int j=v;j<=m;j++)11       dp[j]=max(dp[j],dp[j-v]+w);12 }13 void ZeroOnePack(int v,int w,int m) //01背包14 {15       for(int j=m;j>=v;j--)16        dp[j]=max(dp[j],dp[j-v]+w);17 }18 void MultiPack(int v,int w,int m,int c) //多重背包19 {20     if(v*c>=m) //体积乘以数量大于总体积，说明不能完全装完，相当于有无穷件，用完全背包21      CompletePack(v,w,m);22     else  //可以装完，用01背包23     {24         int k=1;25         while(k<c) //二进制优化26         {27             ZeroOnePack(k*v,k*w,m);28              c-=k;29              k*=2;30         }31         ZeroOnePack(c*v,c*w,m);32     }33 }34 int main()35 {36     int n,i,j,m,k;37     while(scanf("%d%d",&n,&m)!=EOF)38     {39         if(n==0&&m==0) break;40         for(i=0;i<n;i++)41          scanf("%d",&a[i]);  //a[i]既是物体的体积，又是物体的价值42         for(i=0;i<n;i++)43          scanf("%d",&c[i]); //c[i]是物体的数量44         memset(dp,0,sizeof(dp));45         for(i=0;i<n;i++)46         {47             MultiPack(a[i],a[i],m,c[i]);48         }49         int count=0; //计数50         for(i=1;i<=m;i++)51          if(dp[i]==i)  //可以组合且不用找钱52           count++;53         printf("%d\n",count);54     }55     return 0;56 }