HDU 2844 Coins

daybreaking 2018-07-22 原文

Whuacmers use coins.They have coins of value A1,A2,A3…An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn’t know the exact price of the watch.

You are to write a program which reads n,m,A1,A2,A3…An and C1,C2,C3…Cn corresponding to the number of Tony’s coins of value A1,A2,A3…An then calculate how many prices(form 1 to m) Tony can pay use these coins.

InputThe input contains several test cases. The first line of each test case contains two integers n(1 ≤ n ≤ 100),m(m ≤ 100000).The second line contains 2n integers, denoting A1,A2,A3…An,C1,C2,C3…Cn (1 ≤ Ai ≤ 100000,1 ≤ Ci ≤ 1000). The last test case is followed by two zeros.OutputFor each test case output the answer on a single line.Sample Input

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

Sample Output

8
4

可以说是一道多重背包的模板题吧....
然而问题是，如何看出来的它是多重背包。
这里有一个问题，即 背包是求的在当前容量下的最大价值是多少，而不是该容量的背包能有多少种“价格不同的存储方式”。
但是，你可以换一个角度想。
从1～m遍历一遍，对于每一个数，将其当作此时背包的最大容量，判断是否可以满足满足背包恰好装满，如果可以，此时就是一种方案数，如果不可以，也就是说，已有的硬币无法组成这个价格，从而转化成了多重背包问题。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<math.h>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<stack>
 8 #include<deque>
 9 #include<iostream>
10 using namespace std;
11 typedef long long  LL;
12 
13 int value[120];
14 int num[120];
15 int dp[1200000];
16 int n,m;
17 void zeroone_pack(int val,int wei)
18 {
19     int i;
20     for(i=m;i>=wei;i--)
21         dp[i]=max(dp[i],dp[i-wei]+val);
22 }
23 void complete_pack(int val,int wei)
24 {
25     int i;
26     for(i=wei;i<=m;i++)
27     {
28         dp[i]=max(dp[i],dp[i-wei]+val);
29     }
30 }
31 void mul_pack(int val,int wei,int number)
32 {
33     int i,p,j;
34     if(wei*number>=m)
35     {
36         complete_pack(val,wei);
37         return ;
38     }
39     else
40     {
41         int k=1;
42         while(k<=number)
43         {
44             zeroone_pack(k*val,k*wei);
45             number=number-k;
46             k=2*k;
47         }
48         zeroone_pack(number*val,number*wei);
49     }
50 }
51 int main()
52 {
53     int i,p,j,ans;
54     while(scanf("%d%d",&n,&m)!=EOF)
55     {
56         ans=0;
57         if(n==0&&m==0)
58             break;
59         memset(dp,0,sizeof(dp));
60         for(i=0;i<n;i++)
61             scanf("%d",&value[i]);
62         for(i=0;i<n;i++)
63             scanf("%d",&num[i]);
64         for(i=0;i<n;i++)
65         {
66             mul_pack(value[i],value[i],num[i]);
67         }
68         for(i=1;i<=m;i++)
69             if(dp[i]==i)
70                 ans++;
71         printf("%d\n",ans);
72     }
73 }