動(dòng)態(tài)規(guī)劃之01背包問(wèn)題及改進(jìn)-展示頁(yè)
2024-08-06 00:49本頁(yè)面
【正文】 ).....來(lái)依次求解，即可裝包物品分別為（物品n）、（物品n1，n）、（物品n2，n1，n）、……、（物品1，物品2，……物品n1，物品n）。求解最優(yōu)值：設(shè)最優(yōu)值m(i,j)為背包容量為j、可選擇物品為i，i+1，……，n時(shí)的最優(yōu)值(裝入包的最大價(jià)值)。 數(shù)學(xué)描述為： ≤C,且∑ v[i] **第i件物品的重量w[i]0, 價(jià)值v[i]求解將哪些物品裝入背包可使這些物品的重量總和不超過(guò)背包容量，且價(jià)值總和最大。有N件物品和一個(gè)容量為V的背包。第i件物品的重量是w[i]，價(jià)值是v[i]。在選擇裝入背包的物品時(shí)，對(duì)于每種物品i，只能選擇裝包或不裝包，不能裝入多次，也不能部分裝入，因此成為01背包問(wèn)題。形式化描述為：給定n個(gè)物品，背包容量C 0,重量0 , 1≤i≤(X1,X2,…,Xn,), Xi∈{0,1}, 使得 ∑（w[i]Xi） 所以原問(wèn)題的解為m(1，C)將原問(wèn)題分解為其子結(jié)構(gòu)來(lái)求解。最后求出的值即為最優(yōu)值m(1，C)。若求m(i,j)，此時(shí)已經(jīng)求出m(i+1,j)，即第i+1個(gè)物品放入和不放入時(shí)這二者的最大值。j=0,1,2,3……C，分兩種情況：(1)當(dāng)即第i個(gè)物品重量大于背包容量j時(shí)，m(i,j)=m(i+1,j)(2)當(dāng)即第i個(gè)物品重量不大于背包容量j時(shí)，這時(shí)要判斷物品i放入和不放入對(duì)m的影響。所以此時(shí)m(i,j)=m(i+1,jw[i])+v[i]。m(i+1,j)，m(i+1,jw[i])+v[i]總結(jié)得出狀態(tài)轉(zhuǎn)移方程為： ice39。total_value39。select39。2，當(dāng)背包容量C很大時(shí)，算法所需計(jì)算時(shí)間較多。而這些跳躍點(diǎn)取決于在（物品i，物品i+1，……物品n）中選擇放入哪些物品使得在放入重量小于容量 j (0=j=C)的情況下m取得最大值。(m(i,j)j始終小于等于C(1)開始求解時(shí)，先求Pi，初始時(shí)Pn+1={(0，0)}，i=n+1，由此按下列步驟計(jì)算Pi1，Pi2……P1，即Pn，Pn1，……P1(2)求Qi，利用Pi求出m（i，jw[i1]）+v[i1]，即Pi當(dāng)放入物品i1后的變化后的跳躍點(diǎn)集Qi={j+w[i1],)，……}，在函數(shù)圖像上表現(xiàn)為所有跳躍點(diǎn)橫軸坐標(biāo)右移w[i1]，縱軸坐標(biāo)上移v[i1]。此處有個(gè)受控跳躍點(diǎn)的概念：若點(diǎn)(a,b)，(c,d)∈Pi∪Qi，且a=c，bd，則(c,d)受控于(a,b)，所以(c,d)?Pi1。由此計(jì)算得出Pn，Pn1，……，P1。跳躍點(diǎn)的計(jì)算過(guò)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1