dp之多重背包（二进制优化）

void solve(int v,int w,int c)
{
   int count=0;
   for(int k=1;k<=c;k<<=1)
   {
       val[count]=k*v;
       size[count++]=k*w;
       c-=k;
   }
   if(c>0)
   {
       val[count]=c*v;
       size[count++]=c*w;
   }
   for(int i=0;i<count;i++)
   {
       cout<<val[i]<<" "<<size[i]<<endl;
   }
}

多重转为01模版

hdu 3732

思路：因为v，w都是0到10的数，所以会有很多v和w重复，把他们统计出数量，弄成多重背包，然后二进制优化，转为01

#include <string>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <iostream>
using namespace std;
int cnt;
int v[100005];
int w[100005];
int dp[10005];
int n,m;
void change(int a,int b,int c)
{
   int k=1;
   for(k=1;k<=c;k<<=1)
   {
       /*v[cnt]=k*a;
       w[cnt++]=k*b;*/
       for(int j=m;j>=k*b;j--)
       {
           dp[j]=max(dp[j],dp[j-k*b]+k*a);
       }
       c-=k;
   }
   if(c>0)
   {
       /*v[cnt]=k*a;
       w[cnt++]=k*b;*/
       for(int j=m;j>=c*b;j--)
       {
           dp[j]=max(dp[j],dp[j-c*b]+c*a);
       }
   }
   return;
}
int main()
{
   int a,b;
   int map[11][11];
   char s[1005];
   while(~scanf("%d %d",&n,&m))//记得加~或者EOF 不然你怎么优化都是超时
   {
       memset(map,0,sizeof(map));
       memset(dp,0,sizeof(dp));
       cnt=0;
       for(int i=0;i<n;i++)
       {
           scanf("%s %d %d",&s,&a,&b);
           getchar();
           map[a][b]++;
       }
       for(int i=1;i<11;i++)
       {
           for(int j=1;j<11;j++)
           {
               if(map[i][j]>0)
               {
                   int k=1;
                   int c=map[i][j];
                   for(k=1;k<=c;k<<=1)
                   {
                       /*v[cnt]=k*a;
                       w[cnt++]=k*b;*/
                       for(int s=m;s>=k*j;s--)
                       {
                           dp[s]=max(dp[s],dp[s-k*j]+k*i);
                       }
                       c-=k;
                   }
                   if(c>0)
                   {
                       /*v[cnt]=k*a;
                       w[cnt++]=k*b;*/
                       for(int s=m;s>=c*j;s--)
                       {
                           dp[s]=max(dp[s],dp[s-c*j]+c*i);
                       }
                   }
               }
           }
       }
       /*for(int i=0;i<cnt;i++)
       {
           for(int j=m;j>=w[i];j--)
           {
               dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
           }
       }*/
       printf("%d\n",dp[m]);
   }
   return 0;
}

巴特西

dp之多重背包（二进制优化）

最新文章

热门文章