1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define inf 0x3f3f3f3f; 6 using namespace std; 7 int dp[100007]; 8 int val[107]; 9 int cnt[107]; 10 int n,m; 11 void comdp (int w,int v,int m) { 12 for (int i=w;i<=m;i++) 13 dp[i]=max (dp[i],dp[i-w]+v); 14 } 15 void zerodp (int w,int v,int m) { 16 for (int i=m;i-w>=0;i--) { 17 dp[i]=max (dp[i],dp[i-w]+v); 18 } 19 } 20 int main () 21 { 22 while (~scanf ("%d %d",&n,&m)&&(n||m)) { 23 for (int i=1;i<=m;i++) dp[i]=-inf; dp[0]=0; 24 for (int i=1;i<=n;i++) 25 scanf ("%d",&val[i]); 26 for (int i=1;i<=n;i++) 27 scanf ("%d",&cnt[i]); 28 for (int i=1;i<=n;i++) { 29 if (val[i]*cnt[i]>=m) 30 comdp(val[i],val[i],m); // 体积 价值 最大体积 多重背包 31 else { 32 int num=cnt[i]; 33 for (int k=1;k<=num;k*=2 ) { 34 zerodp(k*val[i],k*val[i],m); // 0-1背包 35 num-=k; 36 } 37 if (num) zerodp(num*val[i],num*val[i],m); 38 } 39 } 40 int ans=0; 41 for (int i=1;i<=m;i++) { 42 if (dp[i]>0) ans++; 43 } 44 printf ("%d ",ans); 45 } 46 return 0; 47 }
二进制优化的证明
定理：一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是满足n-2^k+1>0的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。
证明如下：
（1） 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]；
（2）如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1.
（3）如果t>=2^k,设s=n-2^k+1，则t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式。
（证毕！）