動(dòng)態(tài)規(guī)劃之01背包問(wèn)題及改進(jìn)(參考版)
2024-08-02 00:49本頁(yè)面
【正文】 39。)39。,39。(39。p[1]的最后的那個(gè)跳躍點(diǎn)(8,15)即為所求的最優(yōu)值，m(1,C)=15p[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)}將受控跳躍點(diǎn)(5,4)清除后，得到p[4]q[4]=p[4]⊕(6，5)={(6，5)，(10，11)}p[4]={(0,0),(4,6),(9,10)}初始時(shí)p[6]={(0,0)}因此，q[6]=p[6]⊕(w[5],v[5])={(4,6)}舉個(gè)例子n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。求得P1的最后那個(gè)跳躍點(diǎn)即為所求的最優(yōu)值m(1,C)。去掉受控跳躍點(diǎn)，是為了求得在物品i1放入后m較大的點(diǎn)，即 使m取最優(yōu)值的跳躍點(diǎn)。(3)求Pi1，即求Pi∪Qi然后再去掉受控跳躍點(diǎn)后的點(diǎn)集。m(i,j)+v[i1]( )，……}。j,對(duì)于每一個(gè)確定的i值，都有一個(gè)對(duì)應(yīng)的跳躍點(diǎn)集Pi={所以,改進(jìn)算法如下：對(duì)于函數(shù)m(i,j)的值，當(dāng)i確定，j為自變量時(shí)，是單調(diào)不減的跳躍式增長(zhǎng)，如圖所示。當(dāng)C2^n時(shí)，需要Ω(n*2^n)計(jì)算時(shí)間。: vector}但是,該算法有兩個(gè)明顯的缺點(diǎn)：1，基于上述代碼，因?yàn)閿?shù)組索引的需要，要求所給物品重量為整數(shù)。: result[0][capacity], 39。 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))
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1