回溯法解決01背包問題

1、回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。 它在包含問題的所有解的解空間樹中按照深度優(yōu)先的策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一節(jié)點(diǎn)時(shí)， 總是先判斷該節(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，貝U跳過對以該節(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其原先節(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。運(yùn)用回溯法解題通常包含以下三個(gè)步驟：*針對所給問題，定義問題的解空間；確定易于搜索的解空間結(jié)構(gòu)；以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索；在0/1背包問題中，容量為M的背包裝載。從n個(gè)物品中選取裝入背包的物品，物品i的重量為Wi，價(jià)值為Pi。最佳

2、裝載指裝入的物品價(jià)值最高，即XPiXi(i=1.n)取最大值。約束條件為刀WiXi M 且 Xi 0,1(1 i n)。在這個(gè)表達(dá)式中，需求出Xi的值。Xi=1表示物品i裝入背包，Xi = 0表示物品i不裝入背包。即判斷可行解的約束條件是：刀 WiXi 0,Xi 0,1(1 i 0,Xi=0 或 1 (0in )0/1背包問題是一個(gè)自己選取問題，適合于用子集樹表示 0 /1背包問題的解空間。在搜索解空 間樹時(shí)，只要左兒子節(jié)點(diǎn)是一個(gè)可行節(jié)點(diǎn)，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解才 進(jìn)入右子樹搜索，否則將右子樹剪去。程序分析：將物品個(gè)數(shù)，每個(gè)物品體積/價(jià)值輸入，計(jì)算總物品體積 S,輸入背包

3、體積V，如果VS則前置條件錯(cuò)誤，即背包體積輸入錯(cuò)誤，否則順序?qū)⑽锲贩湃氡嘲?。假設(shè)放入前i件物品,背包沒有裝滿，繼續(xù)選取第i+1件物品，若該物品“太大”不能裝入，則棄之繼而選取下一件直到背包裝滿為止；如果剩余物品中找不到合適物品以填滿背包，則說明“剛剛”裝入的第 物品不合適，應(yīng)將i拿出，繼續(xù)從i +1及以后的物品中選取，如此重復(fù)，直到找到滿足條件的 解。回溯求解，物品放入的規(guī)則是“后進(jìn)先出”，所以要用棧存儲符合條件的解剪枝（限界）函數(shù)設(shè)當(dāng)前剩余物品價(jià)值總和為r，當(dāng)前結(jié)點(diǎn)x價(jià)值為cp，當(dāng)前x結(jié)點(diǎn)上界函數(shù)值為bp。L為當(dāng)前 已搜索到的答案結(jié)點(diǎn)中受益的最大值，當(dāng)cp+r=bpL 時(shí)可剪去以X為根的子樹。計(jì)算右子樹中解上界方法是將剩余物品按單位重量價(jià)值排序，一次放入物品直至裝不下為止，再裝入部分未裝入物品直至裝滿背包，由此得到的價(jià)值是右子樹解上界。遞歸方式：遞歸第i+1個(gè) 物品開始打印輸出順序方式:無剪枝函數(shù):有剪枝函數(shù):