多重背包的二进制分组优化

由于多重背包中的不同种物品可能很多，如果一个个遍历将会的得到如下代码：

for(int i=1;i<=n;i++)
  for(int j=0;j<=m;j++)
        for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
            f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);

这存在几个问题：

1. 无法使用一维数组。
2. 时间复杂度为 $O(n^2logK)$

而二进制优化的好处：

1. 优化后可以用01背包问题的方式解决
2. 时间复杂度降到 $O(nlogK)$

二进制优化的本质：将多重背包的朴素算法中对 $k$ 个同种物品的遍历打包为二进制，即将 $k$ 个物品打包为 $[log_2 k]+1$ 个新”物品“。

• 为什么是二进制不是其他进制？ $1,2,...,k$在二进制下是满射的，除了$2^{[log_2 k]} - k$ 之间的数需要补一个数之外，其他的数都可以由2的指数相加得到，并且每个指数至多用到一次。

• 为什么是$[log_2 k]+1$ 个物品？ 对于比小于k的最大2的指数小的数，都可以由2的指数构成，而比这个数大的数，需要补一个数$(k - 2^{[log_2 k]})$ ，用于组成剩余的数。

• ”新物品“有什么特点？ 数量为1，至多取用一个，服从01背包问题的算法

   int cnt=0;
   for(int i=1;i<=n;i++)
   {
       int a,b,s;
       cin>>a>>b>>s;
       int k=1;
       while(k<=s)
       {
           cnt++;
           v[cnt]=k*a;
           w[cnt]=k*b;
           s-=k;
           k*=2;
       }
       if(s!=0)//最大值-小于最大值的最大2的指数，用于补齐数值到最大值
       {
           cnt++;
           w[cnt]=s*b;
           v[cnt]=s*a;
       }
    }
   n=cnt;//将n更新为二进制打包后的“物品压缩包”个数