poj 1742 Coins （多重背包）

http://poj.org/problem?id=1742

ｎ个硬币，面值分别是A1...An,对应的数量分别是C1....Cn.用这些硬币组合起来能得到多少种面值不超过m的方案。

多重背包，不过这题很容易超时，用背包九讲的代码有人说行，但是我提交还是超时，后来参考别人代码加了一些优化才能过，有时间要去搞清楚多重背包的单调队列优化。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 bool dp[100010];
 7 int n,m;
 8 int p[110],q[110];
 9 
10 void ZeroOnePack(int cost)
11 {
12     int i;
13     for(i=m;i>=cost;i--)
14     {
15         dp[i]|=dp[i-cost];
16     }
17 }
18 
19 void CompletePack(int cost)
20 {
21     int i;
22     for(i=cost;i<=m;i++)
23     {
24         dp[i]|=dp[i-cost];
25     }
26 }
27 
28 void MultiplePack(int cost,int amount)
29 {
30     if(cost*amount>=m)
31     {
32         CompletePack(cost);
33         return;
34     }
35     int k=1;
36     while(k<amount)
37     {
38         ZeroOnePack(k*cost);
39         amount-=k;
40         k*=2;
41     }
42     ZeroOnePack(amount*cost);
43 }
44 
45 int main()
46 {
47     int i;
48     while(~scanf("%d%d",&n,&m))
49     {
50         if(n==0&&m==0) break;
51         for(i=0;i<n;i++) scanf("%d",&p[i]);
52         for(i=0;i<n;i++) scanf("%d",&q[i]);
53         for(i=0;i<=m;i++) dp[i]=0;
54        // dp[0]=1;
55         for(i=0;i<n;i++)
56         {
57             MultiplePack(p[i],q[i]);
58         }
59         int res=0;
60         for(i=1;i<=m;i++)
61             if(dp[i]) res++;
62         printf("%d
",res);
63     }
64     return 0;
65 }