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