背包問題（分支限界法）(共6頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上分支限界法01背包問題12軟工 028 胡夢穎一、 問題描述0-1背包問題：給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?在選擇裝入背包的物品時(shí)，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。二、 問題分析分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算法。一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解空間中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束

2、條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法對解空間的搜索方式也不相同。回溯法以深度優(yōu)先的方式搜索解空間，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間。分支限界法的搜索策略是，在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)(分支)，然后再從當(dāng)前的活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，加速搜索的進(jìn)程，在每一個(gè)活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值(限界)，并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。這種方式稱為分支限界法。人們已經(jīng)用分支限

3、界法解決了大量離散最優(yōu)化的問題。三源代碼#include <stdio.h> #include<malloc.h> #define MaxSize 100 /結(jié)點(diǎn)數(shù)的最大值typedef struct QNode float weight;float value;int ceng;struct QNode *parent;bool leftChild;QNode,*qnode;typedef struct qnode QMaxSize; int front,rear; SqQueue; /存放結(jié)點(diǎn)的隊(duì)列 SqQueue sq; float bestv=0; /最優(yōu)解 i

4、nt n=0; /實(shí)際物品數(shù) float wMaxSize; /物品的重量 float vMaxSize; /物品的價(jià)值 int bestxMaxSize; / 存放最優(yōu)解 qnode bestE; void InitQueue(SqQueue &sq ) /隊(duì)列初始化 sq.front=1; sq.rear=1; bool QueueEmpty(SqQueue sq) /隊(duì)列是否為空 if(sq.front=sq.rear) return true; else return false; void EnQueue(SqQueue &sq,qnode b) /入隊(duì) if(sq.

5、front=(sq.rear+1)%MaxSize) printf("隊(duì)列已滿!"); return; sq.Qsq.rear=b; sq.rear=(sq.rear+1)%MaxSize; qnode DeQueue(SqQueue &sq) /出隊(duì) qnode e; if(sq.front=sq.rear) printf("隊(duì)列已空!"); return 0; e=sq.Qsq.front; sq.front=(sq.front+1)%MaxSize; return e; void EnQueue1(float wt,float vt, in

6、t i ,QNode *parent, bool leftchild) qnode b; if (i=n) /可行葉子結(jié)點(diǎn) if (vt=bestv) bestE=parent;bestxn=(leftchild)?1:0; return; b=(qnode)malloc(sizeof(QNode); /非葉子結(jié)點(diǎn) b->weight=wt; b->value=vt; b->ceng=i; b->parent=parent; b->leftChild=leftchild; EnQueue(sq,b); void maxLoading(float w,float v

7、,int c) float wt=0; float vt=0; int i=1; /當(dāng)前的擴(kuò)展結(jié)點(diǎn)所在的層 float ew=0; /擴(kuò)展節(jié)點(diǎn)所相應(yīng)的當(dāng)前載重量 float ev=0; /擴(kuò)展結(jié)點(diǎn)所相應(yīng)的價(jià)值 qnode e=NULL; qnode t=NULL; InitQueue(sq); EnQueue(sq,t); /空標(biāo)志進(jìn)隊(duì)列 while (!QueueEmpty(sq) wt=ew+wi; vt=ev+vi; if (wt <= c) if(vt>bestv) bestv=vt; EnQueue1(wt,vt,i,e,true); / 左兒子結(jié)點(diǎn)進(jìn)隊(duì)列 EnQueue

8、1(ew,ev,i,e,false); /右兒子總是可行； e=DeQueue(sq); / 取下一擴(kuò)展結(jié)點(diǎn) if (e = NULL) if (QueueEmpty(sq) break; EnQueue(sq,NULL); / 同層結(jié)點(diǎn)尾部標(biāo)志 e=DeQueue(sq); / 取下一擴(kuò)展結(jié)點(diǎn) i+; ew=e->weight; /更新當(dāng)前擴(kuò)展結(jié)點(diǎn)的值 ev=e->value; printf("最優(yōu)取法為：n"); for( int j=n-1;j>0;j-) /構(gòu)造最優(yōu)解 bestxj=(bestE->leftChild?1:0); bestE=

9、bestE->parent; for(int k=1;k<=n;k+) if(bestxk=1) printf("物品%d:重量：%.1f，價(jià)值：%.1fn",k,wk,vk); printf("最大價(jià)值為：%.1fn",bestv);void main() int c; float ewvMaxSize; printf("請輸入背包的最大容量v:"); scanf("%d",&c); printf("請輸入物品總數(shù)n:"); scanf("%d",&n); printf("請輸入物品的重量和單位重量價(jià)值:n")