vlambda博客
学习文章列表

由C［i］［j］的递归式(4-11)容易证明：在一般情况下，对每一个确定的i(1≤i≤n)，函数C［i］［j］是关于变量j的阶梯状单调不减函数(事实上，计算C［i］［j］的递归式在变量j是连续变量，即为实数时仍成立)。跳跃点是这一类函数的描述特征。在一般情况下，函数C［i］［j］由其全部跳跃点唯一确定，如图4-9所示。

利用该类函数由其跳跃点唯一确定的性质，来对0-1背包问题的算法knapsack进行改进，具体思路如下： 

(1) 对每一个确定的i(1≤i≤n)，用一个表p［i］来存储函数C［i］［j］的全部跳跃点。对每一个确定的实数j，可以通过查找p［i］来确定函数C［i］［j］的值。p［i］中的全部跳跃点(j，C［i］［j］)按j升序排列。由于函数C［i］［j］是关于j的阶梯状单调不减函数，故p［i］中全部跳跃点的C［i］［j］值也是递增排列的。

(2) p［i］可通过计算p［i-1］得到。初始时令p［0］={(0，0)}。由于函数C［i］［j］是由函数C［i-1］［j］与函数C［i-1］［j-w_i］+v_i做max运算得到的。因此，函数C［i］［j］的全部跳跃点包含于函数C［i-1］［j］的跳跃点集p［i-1］与函数C［i-1］［j-w_i］+v_i的跳跃点集q［i-1］的并集。容易得知，(s，t)∈q［i-1］当且仅当w_i≤s≤W且(s-w_i，t-v_i)∈p［i-1］。因此，容易由p［i-1］来确定跳跃点集q［i-1］，公式为 

(3) 另外，设(a，b)和(c，d)是p［i-1］∪q［i-1］中的两个跳跃点，当c≥a且d<b时，(c，d)受控于(a，b)，从而(c，d)不是p［i］中的跳跃点。也就是说，根据函数c［i］［j］是关于j的阶梯状单调不减函数的特征，在跳跃点集p［i-1］∪q［i-1］中，按j由小到大排序，如果出现j增加，c［i］［j］反而下降的点(j, c［i］［j］)，则不符合函数单调性，要舍弃。p［i-1］∪q［i-1］中的其他跳跃点均为p［i］中的跳跃点。

(4) 由此可得，在递归地由p［i-1］计算p［i］时，可先由p［i-1］计算出q［i-1］，然后合并p［i-1］和q［i-1］，并清除其中的受控跳跃点得到p［i］。

(5) 构造最优解。

第一步，初始时，i=n，j初始化为p［n］中的最大重量，m初始化为p［n］中的最优值。

第二步，检查p［i-1］中的所有点(w，v)，如果w+w_i=j并且v+v_i=m，则x_i=1，j=w，m=v，否则x_i=0。重复第二步，直到i=0为止。

按照算法的改进思路，具体的求解过程如下： 

初始时，令p［0］={(0，0)}。

在该并集中可以看到，跳跃点(2，3)受控于跳跃点(2，6)，因此将(2，3)从并集中清除，得到

在该并集中可以看到，跳跃点(6，5)受控于跳跃点(4，9)，因此将(6，5)从并集中清除，得到

由于跳跃点(13，15)和(15，18)已超出背包的容量W=10，因此将它们清除，得到

在该并集中可以看到，跳跃点(5，4)受控于跳跃点(4，9)，因此将(5，4)从并集中清除，得到

同理，由于跳跃点(11，16)，(12，17)，(13，19)和(14，20)已超出背包的容量W=10，因此将它们清除，得到

在该并集中的受控跳跃点有(4，6)、(7，10)、(8，11)、(9，13)和(10，14)，因此将它们从并集中清除，得到p［5］={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}。

p［5］中最后的跳跃点(8，15)给出了装入背包的最优值15及装入背包的物品重量8。

构造最优解过程：由于p［4］中的(4，9)⊕(4，6)=(8，15)，故x5=1，j=4，m=9；由于p［3］中的所有点⊕(w4，v4)≠(j，m)，故x4=0；p［2］中的所有点⊕(w3，v3)≠(j，m)，故x3=0；p［1］中的(2，6)⊕(2，3)=(4，9)，故x2=1，j=2，m=6；p［0］中的(0，0)⊕(2，6)=(2，6)，故x1=1，j=0，m=0；求得的最优解为(1，1，0，0，1)。

首先定义一个merge_points()函数，完成跳跃点集合的归并排序。接收两个有序的点集，将其归并为一个有序的点集。其代码如下： 

其次，定义knapsack_improve()函数，完成各子问题跳跃点的计算，从而求出原问题的跳跃点，得到问题的最优值。

定义Traceback()函数，根据各子问题的跳跃点，逆向递推构造问题的最优解。其代码如下： 

Python程序入口——main()函数，在main()函数中，给定5个物品的重量、价值和背包的容量，调用 knapsack_improve()函数得到最优值，再调用 Traceback()函数构造问题的最优解，最后将结果打印输出到显示器上。其代码如下： 

输入结果为

最优解为：［1, 1, 0, 0, 1］

实例讲解

精彩回顾

下期预告