動(dòng)態(tài)規(guī)劃之01背包問題及改進(jìn)-在線瀏覽
2024-09-01 00:49本頁面
【正文】 程如下：p[5]={(0,0),(4,6)}q[5]=p[5]⊕(w[4],v[4])={(5,4),(9,10)} p[5]與q[5]的并集p[5]∪q[5]={(0,0),(4,6),(5,4),(9,10)}中跳躍點(diǎn)(5,4)受控于跳躍點(diǎn)(4,6)。p[3]={(0，0)，(4，6)，(9，10)，(10，11)}q[3]=p[3]⊕(2，3)={(2，3)，(6，9)}p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}最后，python代碼的實(shí)現(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_points_q[1])22 return result
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1