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