動態(tài)規(guī)劃之01背包問題及改進(已修改)
2025-08-03 00:49 本頁面
【正文】 有N件物品和一個容量為V的背包。第i件物品的重量是w[i]，價值是v[i]。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大。在選擇裝入背包的物品時，對于每種物品i，只能選擇裝包或不裝包，不能裝入多次，也不能部分裝入，因此成為01背包問題。形式化描述為：給定n個物品，背包容量C 0,重量第i件物品的重量w[i]0, 價值v[i]0 , 1≤i≤(X1,X2,…,Xn,), Xi∈{0,1}, 使得 ∑（w[i]*Xi）≤C,且∑ v[i] *數(shù)學描述為： 求解最優(yōu)值：設(shè)最優(yōu)值m(i,j)為背包容量為j、可選擇物品為i，i+1，……，n時的最優(yōu)值(裝入包的最大價值)。所以原問題的解為m(1，C)將原問題分解為其子結(jié)構(gòu)來求解。要求原問題的解m(1，C)，可從m(n，C)，m(n1，C)，m(n2，C).....來依次求解，即可裝包物品分別為（物品n）、（物品n1，n）、（物品n2，n1，n）、……、（物品1，物品2，……物品n1，物品n）。最后求出的值即為最優(yōu)值m(1，C)。若求m(i,j)，此時已經(jīng)求出m(i+1,j)，即第i+1個物品放入和不放入時這二者的最大值。對于此時背包剩余容量j=0,1,2,3……C，分兩種情況：(1)當w[i] j，即第i個物品重量大于背包容量j時，m(i,j)=m(i+1,j)(2)當w[i] = j，即第i個物品重量不大于背包容量j時，這時要判斷物品i放入和不放入對m的影響?！ ∪舨环湃胛锲穒，則此時m(i,j)=m(i+1,j) 若放入物品i，此時背包剩余容量為 jw[i]，在子結(jié)構(gòu)中已求出當容量k=0,1,2……C 時的最優(yōu)值m(i+1,k)。所以此時m(i,j)=m(i+1,jw[i])+v[i]?！ ∪∩鲜龆叩淖畲笾?，即m(i,j) = max{m(i+1,j)，m(i+1,jw[i])+v[i]}總結(jié)得出狀態(tài)轉(zhuǎn)移方程為： 該算法的python代碼實現(xiàn)： 1 01背包問題 2 __author__ = 39。ice39。
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1