資源描述：
《回溯法解決01背包問題》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、回溯法解決01背包問題回溯法解決01背包問題1、算法思想2、問題描述3、設計實現(xiàn)回溯法解決01背包問題回溯法：是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統(tǒng)搜索，逐層向其原先結點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索。課堂上老師已經(jīng)講解過用回溯法解決n-皇后問題，m-圖著色問題以及哈密頓環(huán)問題，他們有相同的特征即問題的求解目標都
2、是求滿足約束條件的全部可行解。而0/1背包是最優(yōu)化問題，還需要使用限界函數(shù)剪去已能確認不含最優(yōu)答案結點的子樹?；厮莘ń鉀Q0/1背包問題運用回溯法解題通常包含以下三個步驟：a.針對所給問題，定義問題的解空間；b.確定易于搜索的解空間結構；c.以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索；0/1背包問題概述在0/1背包問題中，需對容量為c的背包進行裝載。從n個物品中選取裝入背包的物品，每件物品i的重量為wi,價值為pi。對于可行的背包裝載，背包中的物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即取得
3、最大值。約束條件為c和。在這個表達式中，需求出xi的值。xi=1表示物品i裝入背包中，xi=0表示物品i不裝入背包?；厮莘ń鉀Q01背包問題回溯法解決01背包問題問題舉例最優(yōu)值上界對于0-1背包問題回溯法的一個實例，n=4，M=7，p=[9,10,7,4],w=[3,5,2,1].這4個物品的單位重量價值分別為[3,2,3,5,4].以物品為單位價值的遞減序裝入物品。先裝入物品4，然后裝入物品3和1.裝入這3個物品后，剩余的背包容量為1，只能裝入0.2個物品2.由此可得到一個解為x=[1,0.2,1,1],其相應的價值為22.盡管這不是一
4、個可行解，但可以證明其價值是最有大的上界。因此，對于這個實例，最優(yōu)值不超過22.回溯法解決01背包問題0—1背包問題是一個子集選取問題，適合于用子集樹表示0—1背包問題的解空間。在搜索解空間樹是，只要其左兒子節(jié)點是一個可行結點，搜索就進入左子樹，在右子樹中有可能包含最優(yōu)解是才進入右子樹搜索。否則將右子樹剪去。問題分析：首先是將可供選擇的物品的個數(shù)輸入程序，將物品排成一列，計算總物品的體積s，然后輸入背包的實際體積V，如果背包的體積小于0或者大于物品的總體積s，則判斷輸入的背包體積錯誤，否則開始順序選取物品裝入背包，假設已選取了前i件物品
5、之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品"太大"不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明"剛剛"裝入背包的那件物品"不合適"，應將它取出"棄之一邊"，繼續(xù)再從"它之后"的物品中選取，如此重復，直至求得滿足條件的解。因為回溯求解的規(guī)則是"后進先出"，所以要用到棧來存儲符合條件的解，在存儲過程中，利用數(shù)組來存儲各個物品的體積，然后用深度優(yōu)先的搜索方式求解，將符合條件的數(shù)組元素的下標存入棧里，最后得到符合條件的解并且實現(xiàn)輸出。限界函數(shù)設r是當前剩余物品價值總和；
6、cp是當前結點X的價值；bp是當前X結點上界函數(shù)值。L始終為已搜索到的答案節(jié)點中受益的最大值，當cp+r=bp7、]，p=[18，25，20]且M=20.三個對象的背包問題的解空間10101000101010ABGIFHELDCL=43L=43L=38L=25L=20L=0L=45L=18回溯法解決0/1背包問題#includeintc;//背包容量intn;//物品數(shù)intweight[100];//存放n個物品重量的數(shù)組intprice[100];//存放n個物品價值的數(shù)組intcurrentWeight=0;//當前重量intcurrentPrice=0;//當前價值intbestPrice=0;//當前最優(yōu)值intbest
8、Answer[100];//當前最優(yōu)解intbp=0;intbA[100];//當前最優(yōu)解inttimes=0;回溯法解決01背包問題voidPrint();voidBacktracking(inti){t
