背景：主要是理解了二进制的应用。下次写背包九应该把代码模板化一点了，避免错误。

思路：F[i]=mas{F[i-kC[i]]+kW[i] | 0 =< k <= Mi}，对于每一个容量都求它的最大价值，由于价值和花费是相等的，所以价值只能小于等于花费，那些价值等于花费的就是输字能组成这个数。

学习：1.价值和花费都是本身的值得情况，可以用来判断这些数是否可以组成另一个数。

#include
  
   
#include
   
     #include
    
      using namespace std; int c[109][2],F[100009]; int main(void){ int n,m; while(scanf("%d%d",&n,&m) && n*n+m*m){ for(int i=0;i < n;i++) scanf("%d",&c[i][0]); for(int i=0;i < n;i++) scanf("%d",&c[i][1]
     ); memset(F,0,sizeof(F)); for(int i=0;i < n;i++){ if(c[i][0]*c[i][1] >= m){ for(int j=c[i][0];j <= m;j++){ F[j]=max(F[j],F[j-c[i][0]]+c[i][0]); } }else{ int k=1,key; while(k < c[i][1]){ key=k*c[i][0]; for(int j=m;j >= key;j--) F[j]=max(F[j],F[j-key]+key); c[i][1]-=k; k*=2; } key=c[i][1]*c[i][0]; for(int j=m;j >= key;j--) F[j]=max(F[j],F[j-key]+key); } } int count=0; for(int i=1;i <= m;i++) if(F[i] == i) count++; printf("%d\n",count); } return 0; }