算法设计与分析_3.动态规划1.ppt

* * 3.8 0-1背包问题 （3）算法改进—— 要搞清的几个问题： 受控跳跃点： 设(a，b)和(c，d)是p[i+1]?q[i+1]中的2个跳跃点，则当c?a且db时，(c，d)受控于(a，b)，从而(c，d)不是p[i]中的跳跃点。即，背包容量大，装的物品价值小。 (c，d)肯定不是最优值。 除受控跳跃点外，p[i+1]?q[i+1]中的其它跳跃点均为p[i]中的跳跃点。 * * 3.8 0-1背包问题 （3）算法改进—— 要搞清的几个问题： p[i]的计算：分三步 先由p[i+1]计算出q[i+1] 合并表p[i+1]和表q[i+1] 清除其中的受控跳跃点得到表p[i] p[i] = p[i+1]?q[i+1] * * 3.8 0-1背包问题 m（i，j） 跳跃点（s，t）——（x，m（i，x）） p[i] q[i] 受控跳跃点 p[i] = p[i+1]?q[i+1] （3）算法改进—— 要搞清的几个问题： 例1、 n=3，c=6，w={4，3，2}，v={5，2，1}。 x (0,0) m(4,x) x (2,1) m(4,x-2)+1 x (0,0) (2,1) m(3,x) (3,2) x m(3,x-3)+2 (5,3) x (0,0) (2,1) m(2,x) (3,2) (5,3) x m(2,x-4)+5 (4,5) (6,6) (7,7) (9,8) x (0, 0) (2, 1) m(1,x) (3,2) (5,3) (4,5) (6,6) (7,7) (9,8) x (0,0) (2,1) m(3,x) x (0,0) (2,1) m(2,x) (3,2) (5,3) p[4]={(0, 0)} q[4]=p[4] ? {(w3, v3)} p[3]=p[4] ∪q[4] p[2]=p[3] ∪q[3] p[3]={(0, 0)，(2,1)} q[3]=p[3] ? {(w2, v2)} ={(3,2)(5,3)} p[2]=p[3] ∪q[3] ={(0,0),(2,1),(3,2),(5,3)} p[1]=p[2] ∪q[2] p[2]={(0,0),(2,1),(3,2),(5,3)} q[2]=p[2] ? {(w1, v1)} ={(4,5),(6,6),(7,7),(9,8)} p[1]=p[2] ∪q[2] ={(0,0),(2,1),(3,2),(5,3),(4,5),(6,6)} * * n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。 初始时p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6]?(w5,v5)={(4,6)}。 p[5]={(0,0),(4,6)}。 q[5]=p[5]?(w4,v4)={(5,4),(9,10)}。从跳跃点集p[5]与q[5]的并集p[5]?q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)} 3.8 0-1背包问题 （3）算法改进—— 例子 * * n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。 q[4]=p[4]?(6，5)={(6，5)，(10，11)} p[3]={(0，0)，(4，6)，(9，10)，(10，11)} q[3]=p[3]?(2，3)={(2，3)，(6，9)} p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)} q[2]=p[2]?(2，6)={(2，6)，(4，9)，(6，12)，(8，15)} p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)} p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。 3.8 0-1背包问题 上述算法的主要计算量在于计算跳跃点集p[i](1≤i≤n)。由于q[i+1]=p[i+1]?(wi，vi)，故计算q[i+1]需要O(|p[i+1]|)计算时间。合并p[i+1]和q[i+1]并清除受控跳跃点也需要O(|p[i+1]|)计算时间。从跳跃点集p[i]的定义可以看出，p[i]中的跳跃点相应于xi,…,xn的0/1赋值。因此，p[i]中跳跃点个数不超过2n-i+1。由此可见，算法计算跳跃点集p[i]所花费的计算时间为 从而，改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1≤i≤n)是整数时，|p[i]|≤c+1，(1≤i≤n)。在这种情况下，改进后算法的计算时间复杂性为O(min{nc,2n})。 算法复杂度分析