二进制拆分

在网络上找的我好辛苦啊！！！因为本人太蒟了，看了好多博客都没看懂，然后莫名秒懂。

原理：一个数能够被拆分为任意二进制的和。 (这个原理造出来好多算法啊QAQ)

T=2^p1+2^p2+2^p3+...+2^pn

而且       小于等于       T的所有整数都能被2^p1       2^p2      2^p3      ....     2^pn的和表示出来

证明我不会，但是我知道任意一个数都有自己的二进制形式，比如     13=1101

小于等于13的二进制数肯定不会超过4位，对于T如果有K位，那么小于等于T的数都不可能大于K位

(因为2 ^ 1 + 2 ^ 2 + 2 ^ 3 ...  + 2 ^ p-1   = (2 ^ p)  - 1)

网络上有个例子就是什么：

2^0+2^1+2^2能表示出1到7的任意整数，那么2^0+2^1+2^2+ 6就能表示出1~13的整数

这个例子的剖析就是说：一个数表示拆成小于它的所有二的次方的和(这个二次方的指数要是递增的)后会剩下一个数。

然后我们这样拆分之后就能用log(n)个数表示出 你想表示出来的1~n中的任意数了

放个二进制拆分的例子直观的感受一下它的用途：

多重背包；

众所周知多重背包的朴素算法就是如果第i件物品有 ki 个，那么我们不妨将i物品直接复制为ki个然后做01背包

这样的时间复杂度是O(nmΣki)的；

这玩意很容易超时啊！！！

算法的复杂度瓶颈就在与我们把物品分成ki个做01背包了，

但是你可以把ki进行二进制拆分，把物品栏中加入重量为wi * (2^p),体积为vi *(2^p)的物品了

这样拆分后与拆成ki个物品做零一背包是等效的，因为同样都可以表示出加入当前i物品1~ki个的价值以及重量

然后时间复杂度就优化到了O(nmlog(Σki))

核心代码为:

  for(int i = 1 ; i <= n ; i ++)  
　　 for (int j = 1 ; j <= k[i] ; j <<=1)
　　　t++,val[t]=j*v[i],waste[t]=j*w[i];           

二进制拆分

原文：https://www.cnblogs.com/MYCui/p/13543512.html