HDu -2844 Coins多重背包

这道题是典型的多重背包的题目，也是最基础的多重背包的题目

题目大意：给定n和m，其中n为有多少中钱币， m为背包的容量，让你求出在1 - m 之间有多少种价钱的组合，由于这道题价值和重量相等，所以就是dp[i] = i，其中dp[i]表示当前背包容量为i 的时候背包能装的价值。

题目思路：模板二进制优化

话说那个二进制真的很奇妙，只需要2的1次方到 2的k-1次方，到最后在加上一项当前项的个数 - 2 的k次方 + 1，也就是这些系数分别为1; 2; 2² .....2^k-1;M_i - 2^k + 1，且k是满足M_i - 2^k + 1 > 0的最大整数, 就能表示出所有1 - M_i之间的所有系数，好强大～

代码如下：

 1 #include<iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int MAX = 100000;
 6 int dp[MAX];
 7 int c[MAX], w[MAX];
 8 int v;
 9 
10 void ZeroOnePack(int cost, int wei)
11 {
12     for (int i = v; i >= cost; i--)
13         dp[i] = max(dp[i], dp[i - cost] + wei);
14 }
15 
16 void CompletePack(int cost, int wei)
17 {
18     for (int i = cost; i <= v; i++)
19         dp[i] = max(dp[i], dp[i - cost] + wei);
20 }
21 
22 void MultiPack(int cost, int wei, int cnt)
23 {
24     if (v <= cnt * cost)//如果个数*重量大于背包容量了，直接完全背包
25     {
26         CompletePack(cost, wei);
27     }
28     else
29     {
30         int k = 1;
31         while (k <= cnt)
32         {
33             ZeroOnePack(k *cost, k * wei);
34             cnt = cnt - k;
35             k = 2 * k;
36         }
37         ZeroOnePack(cnt * cost, cnt * wei);
38     }
39 }
40 
41 int main()
42 {
43 
44     int n;
45     while (~scanf("%d %d", &n, &v), n + v)
46     {
47         for (int i = 0; i < n; i++)
48             scanf("%d", &c[i]);
49         for (int i = 0; i < n; i++)
50             scanf("%d", &w[i]);
51         memset(dp, 0, sizeof(dp));
52         for (int i = 0; i< n; i++)
53         {
54             MultiPack(c[i], c[i], w[i]);
55 
56         }
57         int sum = 0;
58         for (int i = 1; i <= v; i++)
59             if (dp[i] == i)
60                 sum++;
61         printf("%d
", sum);
62 
63     }
64 
65     return 0;
66 }