poj1014--01背包二进制拆分，空间压缩

题意描述：
有六种不同价值的珠宝若干，问你能否把这些珠宝分成价值相等的两份。当然，每个珠宝是不能切割的。
非常明显这一题是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.zzzyk.com
假设原来某一种类的珠宝数量为N，我们可以把N拆成1，2，4，8，……，2^(k-1)，N-2^k+1。这些拆分成的数字能够表示1~N之间的任何一个数。
这样，我们就把物品数减小为logN（以2为底，向上取整）。

补充：软件开发 , C++ ,

上一个：C++复习笔记---初始化列表
下一个：[hdu] Find a way （分别从两个点出发BFS，再计算最小值）