回溯法解決背包問題

1、回溯法解決01背包問題回溯法解決01背包問題1 1、算法思想、算法思想2 2、問題描述、問題描述3 3、設(shè)計(jì)實(shí)現(xiàn)、設(shè)計(jì)實(shí)現(xiàn) 回溯法解決01背包問題 回溯法：是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的回溯法：是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對(duì)以該結(jié)定不包含問題的解。如果肯定不包含

2、，則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其原先結(jié)點(diǎn)回溯。否點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其原先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。 課堂上老師已經(jīng)講解過用回溯法解決課堂上老師已經(jīng)講解過用回溯法解決n-皇后問題，皇后問題，m-圖著色問題以及哈密頓環(huán)問題，他們有相同的特征圖著色問題以及哈密頓環(huán)問題，他們有相同的特征即問題的求解目標(biāo)都是求滿足約束條件的全部可行解。即問題的求解目標(biāo)都是求滿足約束條件的全部可行解。而而0/1背包是最優(yōu)化問題，還需要使用限界函數(shù)剪去已背包是最優(yōu)化問題，還需要使用限界函數(shù)剪去已能確認(rèn)不含最優(yōu)答案結(jié)點(diǎn)的

3、子樹。能確認(rèn)不含最優(yōu)答案結(jié)點(diǎn)的子樹?；厮莘ń鉀Q0/1背包問題l運(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à)值最高，即 取得最大值。約束條件為 c和 。 在這個(gè)表達(dá)式中，需求出xi的值。xi=1表示物品i裝入背包中，xi=0表示物品i

4、不裝入背包。niiixp1niiixw1nixi11 , 0回溯法解決01背包問題l回溯法解決01背包問題l問題舉例最優(yōu)值上界l對(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.盡管這不是一個(gè)可行解，但可以證明其價(jià)值是最有大的上界。因此，對(duì)于這個(gè)實(shí)例，最優(yōu)值不超過22.回溯法解決01背包問題l01背包問題是一個(gè)子

5、集選取問題，適合于用子集樹表示01背包問題的解空間。在搜索解空間樹是，只要其左兒子節(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解是才進(jìn)入右子樹搜索。否則將右子樹剪去。問題分析：l首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一列，計(jì)首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一列，計(jì)算總物品的體積算總物品的體積s，然后輸入背包的實(shí)際體積，然后輸入背包的實(shí)際體積V，如果背包的體積，如果背包的體積小于小于0或者大于物品的總體積或者大于物品的總體積s，則判斷輸入的背包體積錯(cuò)誤，否，則判斷輸入的背包體積錯(cuò)誤，否則開始順序選取物品裝入背包，假設(shè)已選取了前則開始順序選取物品裝入背包

6、，假設(shè)已選取了前i 件物品之后背包件物品之后背包還沒有裝滿，則繼續(xù)選取第還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品件物品，若該件物品太大太大不能裝不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明余的物品中找不到合適的物品以填滿背包，則說明剛剛剛剛裝入背包裝入背包的那件物品的那件物品不合適不合適，應(yīng)將它取出，應(yīng)將它取出棄之一邊棄之一邊，繼續(xù)再從，繼續(xù)再從它之后它之后的物品中選取，如此重復(fù)，直至求得滿足條件的解。的物品中選取，如此重復(fù)，直至求得滿足條件的解。l因?yàn)榛厮萸蠼獾囊?guī)則是

7、因?yàn)榛厮萸蠼獾囊?guī)則是后進(jìn)先出后進(jìn)先出，所以要用到棧來存儲(chǔ)符合條件，所以要用到棧來存儲(chǔ)符合條件的解，在存儲(chǔ)過程中，利用數(shù)組來存儲(chǔ)各個(gè)物品的體積，然后用的解，在存儲(chǔ)過程中，利用數(shù)組來存儲(chǔ)各個(gè)物品的體積，然后用深度優(yōu)先的搜索方式求解，將符合條件的數(shù)組元素的下標(biāo)存入棧深度優(yōu)先的搜索方式求解，將符合條件的數(shù)組元素的下標(biāo)存入棧里，最后得到符合條件的解并且實(shí)現(xiàn)輸出。里，最后得到符合條件的解并且實(shí)現(xiàn)輸出。 限界函數(shù)l設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前結(jié)點(diǎn)X的價(jià)值；bp是當(dāng)前X結(jié)點(diǎn)上界函數(shù)值。 L始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，當(dāng)cp+r=bpL時(shí)可剪去以X為根的子樹。l計(jì)算右子樹中解的上界的更好方

8、法是將剩余物品依其單位重量?jī)r(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入該物品的一部分而裝滿背包。由此得到的價(jià)值是右子樹中解的上界。L始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，最優(yōu)解必定大于等于始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，最優(yōu)解必定大于等于L，對(duì)于任意結(jié)點(diǎn)，對(duì)于任意結(jié)點(diǎn)X，若其上界函數(shù)值若其上界函數(shù)值bpL，則可以斷定，則可以斷定X子樹上不含最優(yōu)答案結(jié)點(diǎn)，可以剪去以子樹上不含最優(yōu)答案結(jié)點(diǎn)，可以剪去以X為根的子為根的子樹樹ZYXTbp=cp+rrpcw，cp考察如下背包問題：n=3，w=11，8，6，p=18，25，20且M=20.三個(gè)對(duì)象的背包問題的解空間三個(gè)對(duì)象的背包問題的解空間

9、 1 0 1 0 1 0 0 0 1 0 1 0 1 0ABGIFHELDCL=43L=43L=38L=25L=20L=0L=45L=18回溯法解決0/1背包問題l#include lint c; /背包容量 lint n; /物品數(shù) lint weight100; /存放n個(gè)物品重量的數(shù)組 lint price100; /存放n個(gè)物品價(jià)值的數(shù)組 lint currentWeight=0; /當(dāng)前重量 lint currentPrice=0; /當(dāng)前價(jià)值 lint bestPrice=0; /當(dāng)前最優(yōu)值 lint bestAnswer100; /當(dāng)前最優(yōu)解 lint bp=0;lint bA1

10、00; /當(dāng)前最優(yōu)解 lint times=0;回溯法解決01背包問題l void Print(); lvoid Backtracking(int i) ll times+=1;lif(in) l lPrint();lif(bestPricebp)llbp=bestPrice;lfor(int j=1;j=n;j+)l bAj=bestAnswerj;llreturn; l 回溯法解決01背包問題lif(currentWeight+weighti=c) l /將物品i放入背包，搜索左子樹 lbestAnsweri = 1; lcurrentWeight += weighti; lbestPri

11、ce += pricei; lBacktracking(i+1); /完成上面的遞歸，返回到上一結(jié)點(diǎn)，物品i不放入背包，準(zhǔn)備遞歸右子樹 lcurrentWeight -= weighti; lbestPrice -= pricei; l bestAnsweri = 0; lBacktracking(i+1); l 回溯法解決01背包問題lvoid Print() l int i; lprintf(n路徑為 ); lfor(i=1;in;+i) lprintf(%d,bestAnsweri); lprintf(%dt價(jià)值為%dn,bestAnsweri,bestPrice); l lvoid main() l int i; l/*輸入部分*/l printf(請(qǐng)輸入物品的數(shù)量:n);l scanf(%d,&n);l printf(請(qǐng)輸入背包的容量(能承受的重量):n);l scanf(%d,&c);l printf(請(qǐng)依次輸入%d個(gè)物品的重量:n,n);回溯法解決01背包問題lfor(i=1;i=n;i+)l scanf(%d,&weighti);l printf(請(qǐng)依次輸入%d個(gè)物品的價(jià)值:n,n);l for(i=1;i=n;i+)l scanf(%d,&pricei);lprintf