目? ?錄

回溯算法【0-1背包問(wèn)題】

分支界限算法【0-1背包問(wèn)題】

作業(yè)題（期末考試必考）

小結(jié)

---

回溯算法【0-1背包問(wèn)題】

分支界限算法【0-1背包問(wèn)題】

解決思路：采用優(yōu)先隊(duì)列式分支限界

? 確定目標(biāo)函數(shù)上、下界； ? 確定目標(biāo)函數(shù)的計(jì)算方法；

一般情況下，假設(shè)當(dāng)前已對(duì)前i個(gè)物品進(jìn)行了某種特定的選擇，且背包中已裝入物品的重量是w，獲得的價(jià)值是v，計(jì)算該結(jié)點(diǎn)的目標(biāo)函數(shù)上界的一個(gè)簡(jiǎn)單方法是，將背包中剩余容量全部裝入第i+1個(gè)物品，并可以將背包裝滿，于是，得到限界函數(shù)：

? 依上計(jì)算從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值直到表PT（待處理活結(jié)點(diǎn)列表）中取得極大值。

分支限界法求解0/1背包問(wèn)題算法用偽代碼描述如下：

算法7.1：分枝限界法求解0/1背包問(wèn)題

輸入：n個(gè)物品的重量w[n]，價(jià)值v[n]，背包容量W

輸出：背包獲得的最大價(jià)值和裝入背包的物品

1. 根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的上界up；采用貪心法得到下界down；

2. 計(jì)算根結(jié)點(diǎn)的目標(biāo)函數(shù)值并加入待處理結(jié)點(diǎn)表PT；

3. 循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中取極大值

?? 3.1? i = 表PT中具有最大值的結(jié)點(diǎn)；

?? 3.2 對(duì)結(jié)點(diǎn)i的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作：

???????? 3.2.1 如果結(jié)點(diǎn)x不滿足約束條件，則丟棄該結(jié)點(diǎn)；

???????? 3.2.2 否則，估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值lb，

????????????????? 將結(jié)點(diǎn)x加入表PT中；

4. 將葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)值輸出，回溯求得最優(yōu)解的各個(gè)分量。

作業(yè)題（期末考試必考）

按照優(yōu)先隊(duì)列式（LC）分支限界法求解0-1背包問(wèn)題， 并給出限界函數(shù)，并畫出該實(shí)例的狀態(tài)空間樹。

老師講解此題的板書：

博主課堂筆記（僅供參考）：

背包容量下界的計(jì)算：

背包容量W=16。
①放入物品1(w1=10;v1=100)和物品4(w4=4;v4=12)，背包物品總重量w=14，v=112；
②放入物品2(w1=? 7;v1=63? )和物品4(w4=4;v4=12)，背包物品總重量w=11，v= 75；
③放入物品3(w1=? 8;v1=56? )和物品4(w4=4;v4=12)，背包物品總重量w=12，v= 68。
下界取最大值，即下界w=112。

小結(jié)

回溯算法和分支限界算法在最壞情況下需要遍歷所有的節(jié)點(diǎn)，因此其最壞的算法時(shí)間效率也是指數(shù)級(jí)的。

總結(jié)

以上是生活随笔為你收集整理的分支界限算法【0-1背包问题】按照优先队列式（LC）分支限界法求解0-1背包问题， 并给出限界函数，并画出该实例的状态空间树。的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。