回溯法和分支限界法解決0-1背包題要點(diǎn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上0-1背包問題計(jì)科1班 朱潤華 方法1：回溯法一、回溯法描述：用回溯法解問題時(shí)，應(yīng)明確定義問題的解空間。問題的解空間至少包含問題的一個(gè)（最優(yōu)）解。對(duì)于0-1背包問題，解空間由長度為n的0-1向量組成。該解空間包含對(duì)變量的所有0-1賦值。例如n=3時(shí)，解空間為： （0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1） 然后可將解空間組織成樹或圖的形式，0-1背包則可用完全二叉樹表示其解空間給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問:應(yīng)如何選擇裝入背包的物品，使得裝入背

2、包中物品的總價(jià)值最大?形式化描述：給定c >0, wi >0, vi >0 , 1in.要求找一n元向量(x1,x2,xn,), xi0,1, ? wi xic,且 vi xi達(dá)最大.即一個(gè)特殊的整數(shù)規(guī)劃問題。二、回溯法步驟思想描述：0-1背包問題是子集選取問題。0-1 背包問題的解空間可以用子集樹表示。在搜索解空間樹時(shí)，只要其左兒子節(jié)點(diǎn)是一個(gè)可行節(jié)點(diǎn)，搜索就進(jìn)入左子樹。當(dāng)右子樹中有可能含有最優(yōu)解時(shí)，才進(jìn)入右子樹搜索。否則，將右子樹剪去。設(shè)r是當(dāng)前剩余物品價(jià)值總和，cp是當(dāng)前價(jià)值；bestp是當(dāng)前最優(yōu)價(jià)值。當(dāng)cp+r<=bestp時(shí)，可剪去右子樹。計(jì)算右子樹上界的更好的

3、方法是將剩余物品依次按其單位價(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入物品一部分而裝滿背包。例如：對(duì)于0-1背包問題的一個(gè)實(shí)例，n=4,c=7,p=9,10,7,4,w=3,5,2,1。這4個(gè)物品的單位重量價(jià)值分別為3,2,3,5,4。以物品單位重量價(jià)值的遞減序裝入物品。先裝入物品4，然后裝入物品3和1.裝入這3個(gè)物品后，剩余的背包容量為1，只能裝0.2的物品2。由此得一個(gè)解為1,0.2,1,1，其相應(yīng)價(jià)值為22。盡管這不是一個(gè)可行解，但可以證明其價(jià)值是最優(yōu)值的上界。因此，對(duì)于這個(gè)實(shí)例，最優(yōu)值不超過22。在實(shí)現(xiàn)時(shí)，由Bound計(jì)算當(dāng)前節(jié)點(diǎn)處的上界。類Knap的數(shù)據(jù)成員記錄解空間樹中的節(jié)點(diǎn)

4、信息，以減少參數(shù)傳遞調(diào)用所需要的?？臻g。在解空間樹的當(dāng)前擴(kuò)展節(jié)點(diǎn)處，僅要進(jìn)入右子樹時(shí)才計(jì)算上界Bound,以判斷是否可將右子樹剪去。進(jìn)入左子樹時(shí)不需要計(jì)算上界，因?yàn)樯辖珙A(yù)期父節(jié)點(diǎn)的上界相同。三、回溯法實(shí)現(xiàn)代碼：#include "stdafx.h" #include <iostream> using namespace std; template<class Typew,class Typep> class Knap template<class Typew,class Typep> friend Typep Knapsack(Typep

5、 ,Typew ,Typew,int); private: Typep Bound(int i); void Backtrack(int i); Typew c; /背包容量 int n; /物品數(shù) Typew *w; /物品重量數(shù)組 Typep *p; /物品價(jià)值數(shù)組 Typew cw; /當(dāng)前重量 Typep cp; /當(dāng)前價(jià)值 Typep bestp;/當(dāng)前最后價(jià)值 ; template<class Typew,class Typep> Typep Knapsack(Typep p,Typew w,Typew c,int n); template <class Type

6、> inline void Swap(Type &a,Type &b); template<class Type> void BubbleSort(Type a,int n); int main() int n = 4;/物品數(shù) int c = 7;/背包容量 int p = 0,9,10,7,4;/物品價(jià)值 下標(biāo)從1開始 int w = 0,3,5,2,1;/物品重量 下標(biāo)從1開始 cout<<"背包容量為："<<c<<endl; cout<<"物品重量和價(jià)值分別為："&

7、lt;<endl; for(int i=1; i<=n; i+) cout<<"("<<wi<<","<<pi<<") " cout<<endl; cout<<"背包能裝下的最大價(jià)值為："<<Knapsack(p,w,c,n)<<endl; return 0; template<class Typew,class Typep> void Knap<Typew,Typep>:

8、Backtrack(int i) if(i>n)/到達(dá)葉子節(jié)點(diǎn) bestp = cp; return; if(cw + wi <= c)/進(jìn)入左子樹 cw += wi; cp += pi; Backtrack(i+1); cw -= wi; cp -= pi; if(Bound(i+1)>bestp)/進(jìn)入右子樹 Backtrack(i+1); template<class Typew, class Typep> Typep Knap<Typew, Typep>:Bound(int i)/ 計(jì)算上界 Typew cleft = c - cw; / 剩余

9、容量 Typep b = cp; / 以物品單位重量價(jià)值遞減序裝入物品 while (i <= n && wi <= cleft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i <= n) b += pi/wi * cleft; return b; class Object template<class Typew,class Typep> friend Typep Knapsack(Typep,Typew ,Typew,int); public: int operator <= (Object a)const

10、 return (d>=a.d); private: int ID; float d; ; template<class Typew,class Typep> Typep Knapsack(Typep p,Typew w,Typew c,int n) /為Knap:Backtrack初始化 Typew W = 0; Typep P = 0; Object *Q = new Objectn; for(int i=1; i<=n; i+) Qi-1.ID = i; Qi-1.d = 1.0 * pi/wi; P += pi; W += wi; if(W <= c)/裝

11、入所有物品 return P; /依物品單位重量價(jià)值排序 BubbleSort(Q,n); Knap<Typew,Typep> K; K.p = new Typepn+1; K.w = new Typewn+1; for(int i=1; i<=n; i+) K.pi = pQi-1.ID; K.wi = wQi-1.ID; K.cp = 0; K.cw = 0; K.c = c; K.n = n; K.bestp = 0; /回溯搜索 K.Backtrack(1); delete Q; delete K.w; delete K.p; return K.bestp; temp

12、late<class Type> void BubbleSort(Type a,int n) /記錄一次遍歷中是否有元素的交換 bool exchange; for(int i=0; i<n-1;i+) exchange = false ; for(int j=i+1; j<=n-1; j+) if(aj<=aj-1) Swap(aj,aj-1); exchange = true; /如果這次遍歷沒有元素的交換,那么排序結(jié)束 if(false = exchange) break ; template <class Type> inline void S

13、wap(Type &a,Type &b) Type temp = a; a = b; b = temp; 四、程序運(yùn)行結(jié)果：五、回溯法解決0-1背包問題復(fù)雜度分析：計(jì)算上界需要O(n)時(shí)間，在最壞情況下有O(2n)個(gè)右兒子節(jié)點(diǎn)需要計(jì)算上界，故解0-1背包問題的回溯算法所需要的計(jì)算時(shí)間為O(n2n)。方法2：分支限界法：一、分支限界法描述：給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問:應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?形式化描述：給定c >0, wi >0, vi >0 , 1in.要求找一n元向量(x1,x

14、2,xn,), xi0,1, wi xic,且 vi xi達(dá)最大.即一個(gè)特殊的整數(shù)規(guī)劃問題。二、分支限界法步驟思想：首先，要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量價(jià)值從大到小進(jìn)行排列。在優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下的最大單位重量價(jià)值的物品裝滿剩余容量的價(jià)值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問題的最優(yōu)值。例如：0-1背包問題，當(dāng)n=3時(shí)，w=16,15,15,

15、p=45,25,25, c=30。優(yōu)先隊(duì)列式分支限界法：處理法則:價(jià)值大者優(yōu)先。>A>B,C>C，D，E>C，E>C，J，K>C>F，G>G，L，M>G，M>G>N，O>O>。三、分支限界法解決0-1背包問題實(shí)現(xiàn)代碼：/0-1背包問題 分支限界法求解 #include "stdafx.h" #include "MaxHeap.h" #include <iostream> using namespace std; class Object template<cl

16、ass Typew,class Typep> friend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); public: int operator <= (Object a) const return d>=a.d; private: int ID; float d;/單位重量價(jià)值 ; template<class Typew,class Typep> class Knap; class bbnode friend Knap<int,int> template<class Ty

17、pew,class Typep> friend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); private: bbnode * parent; /指向父節(jié)點(diǎn)的指針 bool LChild; /左兒子節(jié)點(diǎn)標(biāo)識(shí) ; template<class Typew,class Typep> class HeapNode friend Knap<Typew,Typep> public: operator Typep() const return uprofit; private: Typep uprofit

18、, /節(jié)點(diǎn)的價(jià)值上界 profit; /節(jié)點(diǎn)所相應(yīng)的價(jià)值 Typew weight; /節(jié)點(diǎn)所相應(yīng)的重量 int level; /活節(jié)點(diǎn)在子集樹中所處的層序號(hào) bbnode *ptr; /指向活節(jié)點(diǎn)在子集中相應(yīng)節(jié)點(diǎn)的指針 ; template<class Typew,class Typep> class Knap template<class Typew,class Typep> friend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); public: Typep MaxKnapsack(); pr

19、ivate: MaxHeap<HeapNode<Typep,Typew>> *H; Typep Bound(int i); void AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev); bbnode *E; /指向擴(kuò)展節(jié)點(diǎn)的指針 Typew c; /背包容量 int n; /物品數(shù) Typew *w; /物品重量數(shù)組 Typep *p; /物品價(jià)值數(shù)組 Typew cw; /當(dāng)前重量 Typep cp; /當(dāng)前價(jià)值 int *bestx; /最優(yōu)解 ; template <class Type>

20、inline void Swap(Type &a,Type &b); template<class Type> void BubbleSort(Type a,int n); int main() int n = 3;/物品數(shù) int c = 30;/背包容量 int p = 0,45,25,25;/物品價(jià)值 下標(biāo)從1開始 int w = 0,16,15,15;/物品重量 下標(biāo)從1開始 int bestx4;/最優(yōu)解 cout<<"背包容量為："<<c<<endl; cout<<"物品重量和

21、價(jià)值分別為："<<endl; for(int i=1; i<=n; i+) cout<<"("<<wi<<","<<pi<<") " cout<<endl; cout<<"背包能裝下的最大價(jià)值為："<<Knapsack(p,w,c,n,bestx)<<endl; cout<<"此背包問題最優(yōu)解為:"<<endl; for(int i=1;

22、 i<=n; i+) cout<<bestxi<<" " cout<<endl; return 0; template<class Typew,class Typep> Typep Knap<Typew,Typep>:Bound(int i)/計(jì)算節(jié)點(diǎn)所相應(yīng)價(jià)值的上界 Typew cleft = c-cw; /剩余容量高 Typep b = cp; /價(jià)值上界 /以物品單位重量價(jià)值遞減序裝填剩余容量 while(i<=n && wi<=cleft) cleft -= wi; b +

23、= pi; i+; /裝填剩余容量裝滿背包 if(i<=n) b += pi/wi*cleft; return b; /將一個(gè)活節(jié)點(diǎn)插入到子集樹和優(yōu)先隊(duì)列中 template<class Typew,class Typep> void Knap<Typew,Typep>:AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev) bbnode *b = new bbnode; b->parent = E; b->LChild = ch; HeapNode<Typep,Typew> N; N

24、.uprofit = up; N.profit = cp; N.weight = cw; N.level = lev; N.ptr = b; H->Insert(N); /優(yōu)先隊(duì)列式分支限界法，返回最大價(jià)值，bestx返回最優(yōu)解 template<class Typew,class Typep> Typep Knap<Typew,Typep>:MaxKnapsack() H = new MaxHeap<HeapNode<Typep,Typew>>(1000); /為bestx分配存儲(chǔ)空間 bestx = new intn+1; /初始化 i

25、nt i = 1; E = 0; cw = cp = 0; Typep bestp = 0;/當(dāng)前最優(yōu)值 Typep up = Bound(1); /價(jià)值上界 /搜索子集空間樹 while(i!=n+1) /檢查當(dāng)前擴(kuò)展節(jié)點(diǎn)的左兒子節(jié)點(diǎn) Typew wt = cw + wi; if(wt <= c)/左兒子節(jié)點(diǎn)為可行節(jié)點(diǎn) if(cp+pi>bestp) bestp = cp + pi; AddLiveNode(up,cp+pi,cw+wi,true,i+1); up = Bound(i+1); /檢查當(dāng)前擴(kuò)展節(jié)點(diǎn)的右兒子節(jié)點(diǎn) if(up>=bestp)/右子樹可能含有最優(yōu)解

26、AddLiveNode(up,cp,cw,false,i+1); /取下一擴(kuò)展節(jié)點(diǎn) HeapNode<Typep,Typew> N; H->DeleteMax(N); E = N.ptr; cw = N.weight; cp = N.profit; up = N.uprofit; i = N.level; /構(gòu)造當(dāng)前最優(yōu)解 for(int j=n; j>0; j-) bestxj = E->LChild; E = E->parent; return cp; /返回最大價(jià)值，bestx返回最優(yōu)解 template<class Typew,class Ty

27、pep> Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx) /初始化 Typew W = 0; /裝包物品重量 Typep P = 0; /裝包物品價(jià)值 /定義依單位重量價(jià)值排序的物品數(shù)組 Object *Q = new Objectn; for(int i=1; i<=n; i+) /單位重量價(jià)值數(shù)組 Qi-1.ID = i; Qi-1.d = 1.0*pi/wi; P += pi; W += wi; if(W<=c) return P;/所有物品裝包 /依單位價(jià)值重量排序 BubbleSort(Q,n); /創(chuàng)建類Knap的數(shù)據(jù)成員 Knap<Typew,Typep> K; K.p = new Typepn+1; K.w = new Typewn+1; for(int i=1; i<=n; i+) K.pi = pQi-1.ID; K.wi