動態(tài)規(guī)劃之01背包問題及改進(jìn)(完整版)
【正文】 包的物品時，對于每種物品i，只能選擇裝包或不裝包，不能裝入多次，也不能部分裝入，因此成為01背包問題。 若求m(i,j)，此時已經(jīng)求出m(i+1,j)，即第i+1個物品放入和不放入時這二者的最大值。所以此時m(i,j)=m(i+1,jw[i])+v[i]。ice39。j始終小于等于C此處有個受控跳躍點的概念：若點(a,b)，(c,d)∈Pi∪Qi，且a=c，bd，則(c,d)受控于(a,b)，所以(c,d)?Pi1。p[5]={(0,0),(4,6)}q[5]=p[5]⊕(w[4],v[4])={(5,4),(9,10)}最后，python代碼的實現(xiàn)：1 class Point: 2 def __init__(self, x, y): 3 = x 4 = y 5 6 7 01背包問題 改進(jìn) 8 def knapsack_improve(weight, value, capacity): 9 if len(weight) != len(value):10 print(parameter err!)11 return12 obj_num = len(weight)13 jump_points_p = [[] for x in range(obj_num)]14 jump_points_q = [[] for x in range(obj_num)]15 ([Point(0, 0)])16 ([Point(weight[obj_num 1], value[obj_num 1])])17 for i in reversed(list(range(1, obj_num))):18 jump_points_p[i] = merge_points(jump_points_p[i + 1], jump_points_q[i + 1])19 jump_points_q[i] = [Point( + weight[i 1], + value[i 1]) for point in jump_points_p[i] if20 + weight[i 1] = capacity]21 result = merge_points(jump_points_p[1], jump
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1