3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0
8 4
题解：几乎所有博客都是说二进制方式解决，但是很少有人看得懂代码，因为不知道二进制压缩在这里的意义
二进制压缩在这里你只要抓住 1 2 4 8 16 32 .... 2^n 这些数字可以合成 1到2^(n-1)-1中任何数字，
也就是说，在0的基础上用1可以得到0+1=1，然后继续用2可以得到0+2=2和1+2=3，再继续用4可以得到0+4=4和
1+4=5和2+4=6，3+4=4.........这些合成的数字都是正好到下一个2^n的前面一个数字即2^n-1，所以这种做法可以省去
一部分用来参与for循环的数字，最简单的例子，硬币数是x则需要for(i=1;i<=x;i++)一个一个方案遍历，
现在可以for(i=1;i<=x;i*=2)在叠加效果上可以省去i=(3,5,6,7,9....)这些过程
记住，这里的重点就是 “效果叠加”然后省略去模拟那些叠加后产生的效果的步骤
例如：面值是1，个数是6，m=7；
0 1 2 3 4 5 6 7 n x=2^n(用x个此硬币来合成) 效果 省略用来进行for循环的硬币个数数字
dp:0 0 0 0 0 0 0 0 初始
dp:0 1 0 0 0 0 0 0 n=0 2^n=1 此时合成了1~2-1的数 无
dp:0 1 2 3 0 0 0 0 n=1 2^n=2 此时合成了1~4-1的数 3
dp:0 1 2 3 4 5 6 7 n=2 2^n=4 此时合成了1~8-1的数 5 6 7
上面是模拟背包循环的过程，在6以前的2^n最大值是4，由此我们可以把面值确定的那个硬币按1 2 4 8 16 32 ....的数量来取出并01背包，
这样就可以省略其中3 5 6 7 9 10 11 12 13 14....这些硬币个数用来合成的数
注意：但是可以能还有尾巴，如果硬币个数不是正好是2^n呢？像上面，最少需要用到硬币数为8，所以，用 硬币数-最大2^n得到的数字
继续叠加就好了
#include <iostream>
#include <cstring>
using namespace std;
int main (void)
{
int n,m,i,j,k,l;
int a[111],b[111],dp[111111];
while(cin>>n>>m&&(n||m))
{
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
{
cin>>b[i];
if(a[i]*b[i]>m) //如果此硬币总额大于m则作完全背包来压缩01背包
for(j=a[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
else
{
for(j=1;j<=b[i];b[i]-=j,j<<=1) //j:1，2，4，8，16....省略j=(3,5,6,7,9,10,11,12,13,14,15...)
{
for(k=m;k>=a[i]*j;k--) //01背包
dp[k]=max(dp[k],dp[k-a[i]*j]+a[i]*j);
}
for(j=m;j>a[i]*b[i];j--) //把尾巴继续叠加上来
dp[j]=max(dp[j],dp[j-a[i]*b[i]]+a[i]*b[i]);
}
}
k=0;
for(i=1;i<=m;i++)
if(dp[i]==i)k++;
cout<<k<<endl;
}
return 0;
}
HDU--杭电2844--Coins--背包，二进制压缩,布布扣,bubuko.com
原文：http://blog.csdn.net/jingdianitnan/article/details/21156573