动态规划之01背包问题及改进.docx

1、动态规划之01背包问题及改进动态规划之-0-1背包问题及改进有N件物品和一个容量为V的背包。第i件物品的重量是wi，价值是vi。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。在选择装入背包的物品时，对于每种物品i，只能选择装包或不装包，不能装入多次，也不能部分装入，因此成为0-1背包问题。形式化描述为：给定n个物品，背包容量C 0,重量第i件物品的重量wi0, 价值vi0 , 1in.要求找一n元向量(X1,X2,Xn,), Xi0,1, 使得 （wi*Xi）C,且 vi *Xi达最大.即一个特殊的整数规划问题。数学描述为： 求解最优值：设最优值m(i,j)为背包

2、容量为j、可选择物品为i，i+1，n时的最优值(装入包的最大价值)。所以原问题的解为m(1，C)将原问题分解为其子结构来求解。要求原问题的解m(1，C)，可从m(n，C)，m(n-1，C)，m(n-2，C).来依次求解，即可装包物品分别为（物品n）、（物品n-1，n）、（物品n-2，n-1，n）、（物品1，物品2，物品n-1，物品n）。最后求出的值即为最优值m(1，C)。若求m(i,j)，此时已经求出m(i+1,j)，即第i+1个物品放入和不放入时这二者的最大值。对于此时背包剩余容量j=0,1,2,3C，分两种情况：(1)当wi j，即第i个物品重量大于背包容量j时，m(i,j)=m(i+1,

3、j)(2)当wi = j，即第i个物品重量不大于背包容量j时，这时要判断物品i放入和不放入对m的影响。若不放入物品i，则此时m(i,j)=m(i+1,j)若放入物品i，此时背包剩余容量为 j-wi，在子结构中已求出当容量k=0,1,2C 时的最优值m(i+1,k)。所以此时m(i,j)=m(i+1,j-wi)+vi。取上述二者的最大值，即m(i,j) = maxm(i+1,j)，m(i+1,j-wi)+vi总结得出状态转移方程为：该算法的python代码实现： 1 # 0-1背包问题 2 _author_ = ice 3 4 5 # 背包容量0capacity,不是0capacity-1 6

4、def knapsack(weight, value, capacity): 7 if len(weight) != len(value): 8 print(parameter err!) 9 return10 obj_num = len(weight)11 result = for x in range(obj_num)12 divide = min(weight-1, capacity)13 result-1 = 0 for x in range(divide)14 result-1.extend(value-1 for x in range(divide, capacity + 1)15

5、 for i in reversed(list(range(1, obj_num - 1):16 divide = min(weighti, capacity)17 for j in range(divide):18 resulti.append(resulti + 1j)19 for j in range(divide, capacity + 1):20 resulti.append(max(resulti + 1j, resulti + 1j - weighti + valuei)21 22 result0 = capacity: result1capacity23 if weight0

6、2n时，需要(n*2n)计算时间。所以,改进算法如下：对于函数m(i,j)的值，当i确定，j为自变量时，是单调不减的跳跃式增长，如图所示。而这些跳跃点取决于在（物品i，物品i+1，物品n）中选择放入哪些物品使得在放入重量小于容量 j (0=j=C)的情况下m取得最大值。对于每一个确定的i值，都有一个对应的跳跃点集Pi=(j,m(i,j)，。j始终小于等于C(1)开始求解时，先求Pi，初始时Pn+1=(0，0)，i=n+1，由此按下列步骤计算Pi-1，Pi-2P1，即Pn，Pn-1，P1(2)求Qi，利用Pi求出m（i，j-wi-1）+vi-1，即Pi当放入物品i-1后的变化后的跳跃点集Qi=(

7、j+wi-1,m(i,j)+vi-1)，在函数图像上表现为所有跳跃点横轴坐标右移wi-1，纵轴坐标上移vi-1。(3)求Pi-1，即求PiQi然后再去掉受控跳跃点后的点集。此处有个受控跳跃点的概念：若点(a,b)，(c,d)PiQi，且ad，则(c,d)受控于(a,b)，所以(c,d)Pi-1。去掉受控跳跃点，是为了求得在物品i-1放入后m较大的点，即 使m取最优值的跳跃点。由此计算得出Pn，Pn-1，P1。求得P1的最后那个跳跃点即为所求的最优值m(1,C)。举个例子n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。跳跃点的计算过程如下：初始时p6=(0,0)因此，q6=p6

8、(w5,v5)=(4,6)p5=(0,0),(4,6)q5=p5(w4,v4)=(5,4),(9,10)p4=(0,0),(4,6),(9,10)p5与q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p4q4=p4(6，5)=(6，5)，(10，11)p3=(0，0)，(4，6)，(9，10)，(10，11)q3=p3(2，3)=(2，3)，(6，9)p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，1

9、5)p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15)p1的最后的那个跳跃点(8,15)即为所求的最优值，m(1,C)=15最后，python代码的实现：1 class Point: 2 def _init_(self, x, y): 3 self.x = x 4 self.y = y 5 6 7 # 0-1背包问题 改进 8 def knapsack_improve(weight, value, capacity): 9 if len(weight) != len(value):10 print(parameter err!)11 return12 obj_num = le

10、n(weight)13 jump_points_p = for x in range(obj_num)14 jump_points_q = for x in range(obj_num)15 jump_points_p.append(Point(0, 0)16 jump_points_q.append(Point(weightobj_num - 1, valueobj_num - 1)17 for i in reversed(list(range(1, obj_num):18 jump_points_pi = merge_points(jump_points_pi + 1, jump_poin

11、ts_qi + 1)19 jump_points_qi = Point(point.x + weighti - 1, point.y + valuei - 1) for point in jump_points_pi if20 point.x + weighti - 1 = capacity21 result = merge_points(jump_points_p1, jump_points_q1)22 return result23 24 25 def merge_points(points_x, points_y):26 x_len = len(points_x)27 y_len = l

12、en(points_y)28 merged_points = 29 i = j = 030 while True:31 if i = x_len or j = y_len:32 break33 if points_xi.x = points_yj.y:36 j += 137 i += 138 else:39 merged_points.append(points_yj)40 if points_yj.y = points_xi.y:41 i += 142 j += 143 while i merged_points-1.x and points_xi.y merged_points-1.y:4

13、5 merged_points.append(points_xi)46 i += 147 while j merged_points-1.x and points_yj.y merged_points-1.y:49 merged_points.append(points_yj)50 j += 151 return merged_points52 53 54 result = knapsack_improve(2, 2, 6, 5, 4, 6, 3, 5, 4, 6, 10)55 print()56 for point in result:57 print( + str(point.x) + , + str(point.y) + ), end= )58 59 #(0,0) (2,6) (4,9) (6,12) (8,15)