動態(tài)規(guī)劃之01背包問題及改進(jìn)(存儲版)
【正文】 點(5,4)受控于跳躍點(4,6)。由此計算得出Pn，Pn1，……，P1。(1)開始求解時，先求Pi，初始時Pn+1={(0，0)}，i=n+1，由此按下列步驟計算Pi1，Pi2……P1，即Pn，Pn1，……P1(2)求Qi，利用Pi求出m（i，jw[i1]）+v[i1]，即Pi當(dāng)放入物品i1后的變化后的跳躍點集Qi={而這些跳躍點取決于在（物品i，物品i+1，……物品n）中選擇放入哪些物品使得在放入重量小于容量 j (0=j=C)的情況下m取得最大值。total_value39。m(i+1,j)，m(i+1,jw[i])+v[i]j=0,1,2,3……C，分兩種情況：(1)當(dāng) 形式化描述為：給定n個物品，背包容量C 0,重量求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大。≤C,且∑ v[i] * 若不放入物品i，則此時m(i,j)=m(i+1,j) 若放入物品i，此時背包剩余容量為 jw[i]，在子結(jié)構(gòu)中已求出當(dāng)容量k=0,1,2……C 時的最優(yōu)值m(i+1,k)。該算法的python代碼實現(xiàn)： 1 01背包問題 2 __author__ = 39。當(dāng)C2^n時，需要Ω(n*2^n)計算時間。)，……}。(3)求Pi1，即求Pi∪Qi然后再去掉受控跳躍點后的點集。初始時p[6]={(0,0)}因此，q[6]=p[6]⊕(w[5],v[5])={(4,6)}p[1]的最后的那個跳躍點(8,15)即為所求的最優(yōu)值，m(1,C)=15 39。(39。p[4]={(0,0),(4,6),(9,10)}去掉受控跳躍點，是為了求得在物品i1放入后m較大的點，即 使m取最優(yōu)值的跳躍點?！ ∷?改進(jìn)算法如下：對于函數(shù)m(i,j)的值，當(dāng)i確定，j為自變量時，是單調(diào)不減的跳躍式增長，如圖所示。 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(we
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1