hdu 2844（背包）
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int dp[100010],w[110],c[110];int main(){ int n,m,i,j,k,cnt; while( scanf("%d%d",&n,&m),n+m ) { cnt=0; memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) scanf("%d",&w[i]); for(i=1;i<=n;i++) scanf("%d",&c[i]); for(i=1;i<=n;i++) { if( c[i]*w[i] > m ) // 完全背包 { for( j=w[i];j<=m;j++ ) dp[j]= max( dp[j],dp[j-w[i]]+w[i] ); } else //多重背包 转化为 01背包 ，把物品的个数 c[i] 拆分为2^0,2^1,……,2^k,c[i]-2^k+1; 1至c[i]中的数肯定能够分解为前面的数的和。就是十进制转二进制 { k=1; int num=c[i]; while( k < num ) { for( j=m; j>=k*w[i] ; j--) dp[j]=max( dp[j],dp[j-k*w[i]]+k*w[i]); //拆分是对c[i]来说的，具体操作时其实是把2^k个物品组合为一个物品来操作 num-=k; k<<=1; } for( j=m;j>=num*w[i];j--) dp[j]=max( dp[j],dp[j-num*w[i]]+num*w[i] ); } } for(i=1;i<=m;i++) if( dp[i]==i ) cnt++; printf("%d\n",cnt); } return 0;}