题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2844
题意：告诉你n种硬币的面值和数量，可以在1~m中合成出多少中价格
题解：(转)几乎所有博客都是说二进制方式解决，但是很少有人看得懂代码，因为不知道二进制压缩在这里的意义
二进制压缩在这里你只要抓住 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 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstdlib> 6 #include <cmath> 7 #include <set> 8 #include <map> 9 #include <vector> 10 using namespace std; 11 12 int a[110], c[110], dp[1000010]; 13 int main() 14 { 15 int n, m; 16 while(~scanf("%d %d", &n, &m) && (n || m)) 17 { 18 memset(dp, 0, sizeof(dp)); 19 for(int i = 1; i <= n; i++) 20 scanf("%d", a + i); 21 for(int i = 1; i <= n; i++) 22 { 23 scanf("%d", c + i); 24 if(c[i] * a[i] >= m) 25 { 26 for(int j = a[i]; j <= m; j++) 27 dp[j] = max(dp[j], dp[j - a[i]] + a[i]); 28 } 29 else 30 { 31 for(int j = 1; j <= c[i]; c[i] -= j, j <<= 1) 32 { 33 for(int k = m; k >= a[i] * j; k--) 34 dp[k] = max(dp[k], dp[k - a[i] * j] + a[i] * j); 35 } 36 for(int k = m; k >= a[i] * c[i]; k--)//c[i]已经变了 37 dp[k] = max(dp[k], dp[k - a[i] * c[i]] + a[i] * c[i]); 38 } 39 } 40 int sum = 0; 41 for(int i = 1; i <= m; i++) 42 if(dp[i] == i) 43 sum++; 44 printf("%d ", sum); 45 } 46 return 0; 47 }