南阳106

 1 //可转化为多重背包问题即可
 2 #include<stdio.h>
 3 #include<string.h>
 4 int bag[21];
 5 
 6 void multiple_bag(int,int,int,int);
 7 void complete_bag(int,int,int);
 8 void zero_one_bag(int,int,int);
 9 
10 int main()
11 {
12     int n;
13     scanf("%d",&n);
14     while(n--)
15     {
16         memset(bag,0,sizeof bag);
17         int s,Room,val,wei,num;
18         scanf("%d%d",&s,&Room);
19         while(s--)
20         {
21             scanf("%d%d",&val,&wei);
22             num = wei;
23             wei =1;
24             multiple_bag(val,wei,num,Room);
25         }
26         printf("%d
",bag[Room]);
27     }
28 }
29 
30 void multiple_bag(int v,int w,int n,int r)
31 {
32     if(w * n >= r)
33         complete_bag(v,w,r);
34     else
35     {
36         int k=1;
37         while(k*w < n*w)
38         {
39             zero_one_bag(k*v,k*w,r);
40             n-=k;
41             k<<=1;
42         }
43         zero_one_bag(n*v,n*w,r);
44     }
45 }
46 
47 void zero_one_bag(int v,int w,int r)
48 {
49     for(int i=r; i>=w; --i)
50         if(bag[i-w] + v > bag[i])
51             bag[i] = bag[i-w] + v;
52 }
53 
54 void complete_bag(int v,int w,int r)
55 {
56     for(int i=w; i<=r; ++i)
57         if(bag[i-w] + v > bag[i])
58             bag[i] = bag[i-w] + v;
59 }