動態(tài)規(guī)劃之01背包問題及改進(jìn)-wenkub
2022-08-19 00:49:37 本頁面
【正文】 )={(4,6)}將受控跳躍點(5,4)清除后，得到p[4]q[4]=p[4]⊕(6，5)={(6，5)，(10，11)}p[1]的最后的那個跳躍點(8,15)即為所求的最優(yōu)值，m(1,C)=15,39。 39。)39。(39。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[4]={(0,0),(4,6),(9,10)}舉個例子n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。去掉受控跳躍點，是為了求得在物品i1放入后m較大的點，即 使m取最優(yōu)值的跳躍點。m(i,j)+v[i1] j,所以,改進(jìn)算法如下：對于函數(shù)m(i,j)的值，當(dāng)i確定，j為自變量時，是單調(diào)不減的跳躍式增長，如圖所示。: vector}但是,該算法有兩個明顯的缺點：1，基于上述代碼，因為數(shù)組索引的需要，要求所給物品重量為整數(shù)。 3 4 5 背包容量0~capacity,不是0~capacity1 6 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 for i in reversed(list(range(1, obj_num 1))):16 divide = min(weight[i], capacity)17 for j in range(divide):18 result[i].append(result[i + 1][j])19 for j in range(divide, capacity + 1
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1