哈理工oj 1385Leyni, LOLI and Toasts II解题报告多重背包的二进制解法

这是这道题的二进制转化的解法，效率明显要高很多

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 100005
 4 #define M 18
 5 int a[N];
 6 int v[N];
 7 int wei[N];
 8 int max(int a,int b)
 9 {
10     return a>b?a:b;
11 }
12 int main()
13 {
14     int n,m,w,c,t,i,j,k,weight,val;
15     int x,y;
16     scanf("%d",&t);
17     while(t--)
18     {
19         scanf("%d%d%d%d",&n,&m,&w,&c);
20         memset(a,0,sizeof(a));
21         int temp=1;
22         k=0;
23         int t1=n/w;
24         while(temp<=t1)
25         {
26             v[k]=temp*c;
27             wei[k++]=temp*w;
28             t1-=temp;
29             temp<<=1;
30         }
31         if(t1)
32         {
33             v[k]=t1*c;
34             wei[k++]=t1*w;
35         }
36         for(i=1;i<=m;i++)
37         {
38             scanf("%d%d%d%d",&x,&y,&w,&c);
39             temp=1;
40             t1=x/y;
41             while(temp<=t1)
42         {
43             v[k]=temp*c;
44             wei[k++]=temp*w;
45             t1-=temp;
46             temp<<=1;
47         }
48         if(t1)
49         {
50             v[k]=t1*c;
51             wei[k++]=t1*w;
52         }
53         }
54         for(i=0;i<k;i++)
55         for(j=n;j>=wei[i];j--)
56         a[j]=max(a[j],a[j-wei[i]]+v[i]);
57         printf("%d\n",a[n]);
58     }
59     return 0;
60 }