HDU 2844/POJ 1742 Coins

                  
思路：多重背包+二進制優化

[cpp]
; 
int c[110],v[110],n,m,sum; 
int completepack(int a,int sum) 
{ 
   int i; 
   for(i=a;i<=m;i++) 
   { 
      if(dp[i-a]+a>dp[i]) 
      { 
         dp[i]=dp[i-a]+a; 
         if(dp[i]==i) sum++; 
      } 
   } 
   return sum; 
} 
int pack01(int k,int a,int sum) 
{ 
   int i,t=k*a; 
   for(i=m;i>=t;i--) 
   { 
      if(dp[i]<dp[i-t]+t) 
      { 
          dp[i]=dp[i-t]+t; 
          if(dp[i]==i) sum++; 
      } 
   } 
    return sum; 
} 
int main() 
{ 
   int i,k; 
   while(scanf("%d%d",&n,&m)&&(n+m)) 
   { 
      for(i=1;i<=n;i++) 
        scanf("%d",&v[i]); 
      for(i=1;i<=n;i++) 
          scanf("%d",&c[i]); 
      memset(dp,0,sizeof(dp)); 
      sum=0; 
      for(i=1;i<=n;i++) 
      { 
         if(v[i]*c[i]>=m) 
             sum=completepack(v[i],sum); 
         else  
         { 
           k=1; 
           int count=c[i]; 
           while(k<count) 
           { 
              sum=pack01(k,v[i],sum); 
              count=count-k; 
              k=k<<1; 
           } 
           sum=pack01(count,v[i],sum); 
         } 
      } 
       printf("%d\n",sum); 
   } 
   return 0; 
}