遞歸法求01背包問(wèn)題_第1頁(yè)
遞歸法求01背包問(wèn)題_第2頁(yè)
遞歸法求01背包問(wèn)題_第3頁(yè)
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說(shuō)明：本文檔由用戶(hù)提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

遞歸法求01背包問(wèn)題一、問(wèn)題描述0/1背包問(wèn)題：現(xiàn)有n種物品，對(duì)1<=i<=n,已知第i種物品的重量為正整數(shù)叫，價(jià)值為正整數(shù)*,背包能承受的最大載重量為正整數(shù)W,現(xiàn)要求找出這n種物品的一個(gè)子集，使得子集中物品的總重量不超過(guò)W且總價(jià)值盡量大。（注意：這里對(duì)每種物品或者全取或者一點(diǎn)都不取，不允許只取一部分）遞歸法：在利用遞歸法解決0-1背包問(wèn)題時(shí)，我們可以先從第n個(gè)物品看起。每次的遞歸調(diào)用都會(huì)判斷兩種情況：（1）背包可以放下第n個(gè)物品，則x[n]=1，并繼續(xù)遞歸調(diào)用物品重量為W-w[n],物品數(shù)目為n-1的遞歸函數(shù)，并返回此遞歸函數(shù)值與v[n]的和作為背包問(wèn)題的最優(yōu)解；（2）背包放不下第n個(gè)物品，則x[n]=0，并繼續(xù)遞歸調(diào)用背包容量為W，物品數(shù)目為n-1的遞歸函數(shù)，并返回此遞歸函數(shù)值最為背包問(wèn)題的最優(yōu)解。遞歸調(diào)用的終結(jié)條件是背包的容量為0或物品的數(shù)量為0.此時(shí)就得到了0-1背包問(wèn)題的最優(yōu)解。用遞歸法解0-1背包問(wèn)題可以歸結(jié)為下函數(shù)：

IKnapSack(n—1,m)KnapSack(n,m)=<IKnapSack(n—1,m—w[n])+v[n]沒(méi)有選擇物品n選擇了物品n第一個(gè)式子表示選擇物品n后得到價(jià)值KnapSack(n—1,m—w[n])+v[n]比不選擇物品n情況下得到的價(jià)值KnapSack(n—1,m)小，所以最終還是不選擇物品n;第二個(gè)式子剛好相反，選擇物品n后的價(jià)值KnapSack(n—1,m-w[n])+v[n]不小于不選擇物品n情況下得到了價(jià)值KnapSack(n—1,m)沒(méi)有選擇物品n選擇了物品n在遞歸調(diào)用的過(guò)程中可以順便求出所選擇的物品。下面是標(biāo)記物品被選情況的數(shù)組x[n]求解的具體函數(shù)表示：10KnapSack(n,m)=KnapSack(n—1,m)X[n]=lT[1KnapSack(n,m)=KnapSack(n—1,m一w[n])+v[n]在函數(shù)中，遞歸調(diào)用的主體函數(shù)為KnapSack，m表示背包的容量，n表示物品的數(shù)量，x[n]表示是否選擇了第n個(gè)物品(1一選，0一不選)。每個(gè)物品的重

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論