在網絡上找的我好辛苦啊！！！因為本人太蒟了，看了好多部落格都沒看懂，然後莫名秒懂。
原理：一個數能夠被拆分為任意二進制的和。 (這個原理造出來好多算法啊QAQ)
T=2p1+2p2+2p3+...+2pn
而且 小于等于 T的所有整數都能被2p1 2p2 2p3 .... 2pn的和表示出來
證明我不會，但是我知道任意一個數都有自己的二進制形式，比如 13=1101
小于等于13的二進制數肯定不會超過4位，對于T如果有K位，那麼小于等于T的數都不可能大于K位
(因為21 + 22 + 23 ... + 2p-1 = 2p - 1)
網絡上有個例子就是什麼：
20+21+22能表示出1到7的任意整數，那麼20+21+22+ 6就能表示出1~13的整數
這個例子的剖析就是說：
一個數表示拆成小于它的所有二的次方的和(這個二次方的指數要是遞增的)後會剩下一個數。
然後我們這樣拆分之後就能用log(n)個數表示出 你想表示出來的1~n中的任意數了
放個二進制拆分的例子直覺的感受一下它的用途：
多重背包；
衆所周知多重背包的樸素算法就是如果第i件物品有 ki 個，那麼我們不妨将i物品直接複制為ki個然後做01背包
這樣的時間複雜度是O(nmΣki)的；
這玩意很容易逾時啊！！！
算法的複雜度瓶頸就在與我們把物品分成ki個做01背包了，
但是你可以把ki進行二進制拆分，把物品欄中加入重量為wi * (2p),體積為vi *(2p)的物品了
這樣拆分後與拆成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];