回溯算法 0-1 背包算法 c

1、回溯算法 0-1 背包算法 2009-12-03 10:38:04 閱讀218 評論0 字號：大中小 訂閱 .【實驗?zāi)康摹繉W(xué)習(xí)掌握回溯算法。 【實驗內(nèi)容】用回溯法求解01背包問題，并輸出問題的最優(yōu)解。01背包問題描述如下：給定n種物品和一背包。物品i的重量是Wi，其價值為Vi，背包的容量是c，問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大。 【實驗條件】 【需求分析】對于給定n種物品和一背包。在容量最大值固定的情況下，要求裝入的物品價值最大化。 【設(shè)計原理】一、回溯法： 回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)

2、點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。 二、算法框架： 1、問題的解空間：應(yīng)用回溯法解問題時，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)到少包含問題的一個（最優(yōu)）解。 2、回溯法的基本思想

3、：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點(diǎn)就成為一個活結(jié)點(diǎn)，同時也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個新結(jié)點(diǎn)。這個新結(jié)點(diǎn)就成為一個新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。換句話說，這個結(jié)點(diǎn)不再是一個活結(jié)點(diǎn)。此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點(diǎn)處，并使這個活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時為止。 運(yùn)用回溯法解題通常包含以下三個步驟： （1）針對所給問題，定義問題

4、的解空間； （2）確定易于搜索的解空間結(jié)構(gòu)； （3）以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索； 3、遞歸回溯：由于回溯法是對解空間的深度優(yōu)先搜索，因此在一般情況下可用遞歸函數(shù)來實現(xiàn)回溯法?！靖乓O(shè)計】01背包問題是一個子集選取問題，適合于用子集樹表示01背包問題的解空間。在搜索解空間樹是，只要其左兒子節(jié)點(diǎn)是一個可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解是才進(jìn)入右子樹搜索。否則將右子樹剪去。int c;/背包容量 int n; /物品數(shù) int *w;/物品重量數(shù)組 int *p;/物品價值數(shù)組 int cw;/當(dāng)前重量 int cp;/當(dāng)前價值 int b

5、estp;/當(dāng)前最優(yōu)值 int *bestx;/當(dāng)前最優(yōu)解 int *x;/當(dāng)前解 int Knap:Bound(int i)/計算上界void Knap:Backtrack(int i)/回溯 int Knapsack(int p,int w,int c,int n) /為Knap:Backtrack初始化 【詳細(xì)設(shè)計】#includeusing namespace std; class Knapfriend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m=n;m+) coutbestxm

6、; coutendl; ; private: int Bound(int i); void Backtrack(int i); int c;/背包容量 int n; /物品數(shù) int *w;/物品重量數(shù)組 int *p;/物品價值數(shù)組 int cw;/當(dāng)前重量 int cp;/當(dāng)前價值 int bestp;/當(dāng)前最優(yōu)值 int *bestx;/當(dāng)前最優(yōu)解 int *x;/當(dāng)前解 ; int Knap:Bound(int i) /計算上界 int cleft=c-cw;/剩余容量 int b=cp; /以物品單位重量價值遞減序裝入物品 while(i=n&wi=cleft) cleft-=wi;

7、 b+=pi; i+; /裝滿背包 if(in) if(bestpcp) for(int j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/搜索右子樹 xi=0; Backtrack(i+1); class Object friend int Knapsack(int p,int w,int c,int n);public: int operator=a.d); private: int ID; float d; int Knapsack(int p,int w,int c,int n) /為Knap:Backtrack初始化 in

8、t W=0; int P=0; int i=1; Object *Q=new Objectn; for(i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W=c) return P;/裝入所有物品 /依物品單位重量排序 float f; for( i=0;in;i+) for(int j=i;jn;j+) if(Qi.dQj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K; K.p = new intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new intn+1; K.x0=0; K.bestx0=0; for( 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); K.print(); delete Q; delete K.w; delete K.p; return K.bestp; void main() int *p; int *w; int c=0; int n=0; int i=0; cout請輸入背包個數(shù)：n; p=new i