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

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

阅读量：4696 次

发布时间：2019-06-09

本文共 1351 字，大约阅读时间需要 4 分钟。

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

View Code

1 #include
      
        2 #include
       
         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
        
         =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 }