題意描述：
有六種不同價值的珠寶若干，問你能否把這些珠寶分成價值相等的兩份。當然，每個珠寶是不能切割的。
非常明顯這一題是01背包問題，由於珠寶數量巨大，為了提高程序效率，我們要對同種價值的珠寶進行二進制拆分，這樣能夠迅速減少珠寶的數量（具體說來珠寶數量會變成O(logN)的數量級，N是原來珠寶的個數），二進制拆分後與原來是等效的，想想二進制數就明白了。
01背包的狀態轉移方程為：
當v<Ci時f[i,v]=f[i-1,v];(1)
當v>=Ci時f[i,v]=Max(f[i-1,v],f[i-1,v-Ci]+Wi);(2)//當第i件物品能夠放下時，我們可以選擇放，或不放，取決於總價值的大小。
其中v為當前背包的中容量，Ci表示第i件物品的體積，Wi表示第i件物品的價值，f[i,v]表示容量為v的背包在考慮前i件物品後的最大價值。
上面的狀態轉移方程實現起來要開一個大小為I*V的二維數組（I為物品總個數，V為背包的總體積），可是有時候I和V可能很大，我們就需要很大的空間，甚至有可能超出范圍，其實在只考慮最終價值不關心到底選了那幾件物品時，上面轉移方程的空間是可以壓縮的。我們看到當考慮物品i時，我們用到的狀態只與第i-1件物品有關，因此空間壓縮的狀態轉移方程為：
當v<Ci時f[v]=f[v];(3)
當v>=Ci時f[v]=Max(f[v],f[v-Ci]+Wi);(4)
利用(4)的時候求解順序很重要，要按v從大到小求，這樣才能保證前面的狀態不被覆蓋。
這裡說一下二進制拆分www.2cto.com
假設原來某一種類的珠寶數量為N，我們可以把N拆成1，2，4，8，……，2^(k-1)，N-2^k+1。這些拆分成的數字能夠表示1~N之間的任何一個數。
這樣，我們就把物品數減小為logN（以2為底，向上取整）。
