動態(tài)規(guī)劃之01背包問題及改進(編輯修改稿)
2024-08-18 00:49 本頁面
【文章內(nèi)容簡介】 y_temp = weight[i]32 33 if capacity_temp == 0:34 vector[1] = 035 else:36 vector[1] = 137 38 return {39。total_value39。: result[0][capacity], 39。select39。: vector}但是,該算法有兩個明顯的缺點：1，基于上述代碼，因為數(shù)組索引的需要，要求所給物品重量為整數(shù)。2，當(dāng)背包容量C很大時，算法所需計算時間較多。當(dāng)C2^n時，需要Ω(n*2^n)計算時間。所以,改進算法如下：對于函數(shù)m(i,j)的值，當(dāng)i確定，j為自變量時，是單調(diào)不減的跳躍式增長，如圖所示。而這些跳躍點取決于在（物品i，物品i+1，……物品n）中選擇放入哪些物品使得在放入重量小于容量 j (0=j=C)的情況下m取得最大值。對于每一個確定的i值，都有一個對應(yīng)的跳躍點集Pi={(j,m(i,j))，……}。j始終小于等于C (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={(j+w[i1],m(i,j)+v[i1])，……}，在函數(shù)圖像上表現(xiàn)為所有跳躍點橫軸坐標(biāo)右移w[i1]，縱軸坐標(biāo)上移v[i1]。(3)求Pi1，即求Pi∪Qi然后再去掉受控跳躍點后的點集。此處有個受控跳躍點的概念：若點(a,b)，(c,d)∈Pi∪Qi，且a=c，bd，則(c,d)受控于(a,b)，所以(c,d)?Pi1。去掉受控跳躍點，是為了求得在物品i1放入后m較大的點，即 使m取最優(yōu)值的跳躍點。由此計算得出Pn，Pn1，……，P1。求得P1的最后那個跳躍點即為所求的最優(yōu)值m(1,C)。舉個例子n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。跳躍點的計算過程如下：初始時p[6]={(0,0)}因此，q[6]=p[6]⊕(w[5],v[5])={(4,6)}p[5]={(0,0),(4,6)}q[5]=p[5]⊕(w[4],v[4])={(5,4),(9,10)}p[4]={(0,0),(4,6),(9,10)} p[5]與q[5]的并集p[5]∪q[5]={(0,0),(4,6),(5,4
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1