回溯法解決01背包問題

《回溯法解決01背包問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、回溯法解決01背包問題回溯法解決01背包問題1、算法思想2、問題描述3、設(shè)計(jì)實(shí)現(xiàn)回溯法解決01背包問題回溯法：是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其原先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。課堂上老師已經(jīng)講解過用回溯法解決n-皇后問題，m-圖著色問題以及哈密頓環(huán)問題，他們有相同的特征即問題的求解目標(biāo)都

2、是求滿足約束條件的全部可行解。而0/1背包是最優(yōu)化問題，還需要使用限界函數(shù)剪去已能確認(rèn)不含最優(yōu)答案結(jié)點(diǎn)的子樹。回溯法解決0/1背包問題運(yùn)用回溯法解題通常包含以下三個(gè)步驟：a.針對(duì)所給問題，定義問題的解空間；b.確定易于搜索的解空間結(jié)構(gòu)；c.以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索；0/1背包問題概述在0/1背包問題中，需對(duì)容量為c的背包進(jìn)行裝載。從n個(gè)物品中選取裝入背包的物品，每件物品i的重量為wi,價(jià)值為pi。對(duì)于可行的背包裝載，背包中的物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價(jià)值最高，即取得

3、最大值。約束條件為c和。在這個(gè)表達(dá)式中，需求出xi的值。xi=1表示物品i裝入背包中，xi=0表示物品i不裝入背包。回溯法解決01背包問題回溯法解決01背包問題問題舉例最優(yōu)值上界對(duì)于0-1背包問題回溯法的一個(gè)實(shí)例，n=4，M=7，p=[9,10,7,4],w=[3,5,2,1].這4個(gè)物品的單位重量?jī)r(jià)值分別為[3,2,3,5,4].以物品為單位價(jià)值的遞減序裝入物品。先裝入物品4，然后裝入物品3和1.裝入這3個(gè)物品后，剩余的背包容量為1，只能裝入0.2個(gè)物品2.由此可得到一個(gè)解為x=[1,0.2,1,1],其相應(yīng)的價(jià)值為22.盡管這不是一

4、個(gè)可行解，但可以證明其價(jià)值是最有大的上界。因此，對(duì)于這個(gè)實(shí)例，最優(yōu)值不超過22.回溯法解決01背包問題0—1背包問題是一個(gè)子集選取問題，適合于用子集樹表示0—1背包問題的解空間。在搜索解空間樹是，只要其左兒子節(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解是才進(jìn)入右子樹搜索。否則將右子樹剪去。問題分析：首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一列，計(jì)算總物品的體積s，然后輸入背包的實(shí)際體積V，如果背包的體積小于0或者大于物品的總體積s，則判斷輸入的背包體積錯(cuò)誤，否則開始順序選取物品裝入背包，假設(shè)已選取了前i件物品

5、之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品"太大"不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明"剛剛"裝入背包的那件物品"不合適"，應(yīng)將它取出"棄之一邊"，繼續(xù)再從"它之后"的物品中選取，如此重復(fù)，直至求得滿足條件的解。因?yàn)榛厮萸蠼獾囊?guī)則是"后進(jìn)先出"，所以要用到棧來存儲(chǔ)符合條件的解，在存儲(chǔ)過程中，利用數(shù)組來存儲(chǔ)各個(gè)物品的體積，然后用深度優(yōu)先的搜索方式求解，將符合條件的數(shù)組元素的下標(biāo)存入棧里，最后得到符合條件的解并且實(shí)現(xiàn)輸出。限界函數(shù)設(shè)r是當(dāng)前剩余物品價(jià)值總和；

6、cp是當(dāng)前結(jié)點(diǎn)X的價(jià)值；bp是當(dāng)前X結(jié)點(diǎn)上界函數(shù)值。L始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，當(dāng)cp+r=bp

7、]，p=[18，25，20]且M=20.三個(gè)對(duì)象的背包問題的解空間10101000101010ABGIFHELDCL=43L=43L=38L=25L=20L=0L=45L=18回溯法解決0/1背包問題#includeintc;//背包容量intn;//物品數(shù)intweight[100];//存放n個(gè)物品重量的數(shù)組intprice[100];//存放n個(gè)物品價(jià)值的數(shù)組intcurrentWeight=0;//當(dāng)前重量intcurrentPrice=0;//當(dāng)前價(jià)值intbestPrice=0;//當(dāng)前最優(yōu)值intbest

8、Answer[100];//當(dāng)前最優(yōu)解intbp=0;intbA[100];//當(dāng)前最優(yōu)解inttimes=0;回溯法解決01背包問題voidPrint();voidBacktracking(inti){t