hdu 2844(多重背包）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2844

思路：其实就是多重背包的应用，只是这里价值和重量是相等的，因此最后计数是要计价值和重量相等的个数；

View Code

 1 #include<iostream>
 2 #include<algorithm>
 3 const int N=100010;
 4 using namespace std;
 5 int n,m;
 6 
 7 struct Node{
 8     int value;
 9     int number;
10 }node[N/100];
11 int dp[N];
12 
13 //完全背包
14 void CompletePack(int value){
15     for(int i=value;i<=m;i++){
16         dp[i]=max(dp[i],dp[i-value]+value);
17     }
18 }
19 
20 //01背包
21 void ZeroOnePack(int value){
22     for(int i=m;i-value>=0;i--){
23         dp[i]=max(dp[i],dp[i-value]+value);
24     }
25 }
26 
27 //多重背包
28 void MultiplePack(int value,int number){
29     //如果>=m,就按完全背包处理
30     if(value*number>=m){
31         CompletePack(value);
32         return ;
33     }
34     int k=1;
35     while(k<number){
36         ZeroOnePack(k*value);
37         number-=k;
38         k<<=1;
39     }
40     ZeroOnePack(number*value);
41 }
42 
43 int main(){
44     while(scanf("%d%d",&n,&m)!=EOF){
45         if(n==0&&m==0)break;
46         for(int i=0;i<n;i++){
47             scanf("%d",&node[i].value);
48         }
49         for(int i=0;i<n;i++){
50             scanf("%d",&node[i].number);
51         }
52         memset(dp,0,sizeof(dp));
53         for(int i=0;i<n;i++){
54             MultiplePack(node[i].value,node[i].number);
55         }
56         int count=0;
57         for(int i=1;i<=m;i++){
58             if(dp[i]==i)count++;
59         }
60         printf("%d\n",count);
61     }
62     return 0;
63 }