背包问题（分支限界法）(共6页)

1、精选优质文档-倾情为你奉上分支限界法01背包问题12软工 028 胡梦颖一、 问题描述0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。二、 问题分析分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束

2、条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。这种方式称为分支限界法。人们已经用分支限

3、界法解决了大量离散最优化的问题。三源代码#include <stdio.h> #include<malloc.h> #define MaxSize 100 /结点数的最大值typedef struct QNode float weight;float value;int ceng;struct QNode *parent;bool leftChild;QNode,*qnode;typedef struct qnode QMaxSize; int front,rear; SqQueue; /存放结点的队列 SqQueue sq; float bestv=0; /最优解 i

4、nt n=0; /实际物品数 float wMaxSize; /物品的重量 float vMaxSize; /物品的价值 int bestxMaxSize; / 存放最优解 qnode bestE; void InitQueue(SqQueue &sq ) /队列初始化 sq.front=1; sq.rear=1; bool QueueEmpty(SqQueue sq) /队列是否为空 if(sq.front=sq.rear) return true; else return false; void EnQueue(SqQueue &sq,qnode b) /入队 if(sq.

5、front=(sq.rear+1)%MaxSize) printf("队列已满!"); return; sq.Qsq.rear=b; sq.rear=(sq.rear+1)%MaxSize; qnode DeQueue(SqQueue &sq) /出队 qnode e; if(sq.front=sq.rear) printf("队列已空!"); 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) /可行叶子结点 if (vt=bestv) bestE=parent;bestxn=(leftchild)?1:0; return; b=(qnode)malloc(sizeof(QNode); /非叶子结点 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; /当前的扩展结点所在的层 float ew=0; /扩展节点所相应的当前载重量 float ev=0; /扩展结点所相应的价值 qnode e=NULL; qnode t=NULL; InitQueue(sq); EnQueue(sq,t); /空标志进队列 while (!QueueEmpty(sq) wt=ew+wi; vt=ev+vi; if (wt <= c) if(vt>bestv) bestv=vt; EnQueue1(wt,vt,i,e,true); / 左儿子结点进队列 EnQueue

8、1(ew,ev,i,e,false); /右儿子总是可行； e=DeQueue(sq); / 取下一扩展结点 if (e = NULL) if (QueueEmpty(sq) break; EnQueue(sq,NULL); / 同层结点尾部标志 e=DeQueue(sq); / 取下一扩展结点 i+; ew=e->weight; /更新当前扩展结点的值 ev=e->value; printf("最优取法为：n"); for( int j=n-1;j>0;j-) /构造最优解 bestxj=(bestE->leftChild?1:0); bestE=

9、bestE->parent; for(int k=1;k<=n;k+) if(bestxk=1) printf("物品%d:重量：%.1f，价值：%.1fn",k,wk,vk); printf("最大价值为：%.1fn",bestv);void main() int c; float ewvMaxSize; printf("请输入背包的最大容量v:"); scanf("%d",&c); printf("请输入物品总数n:"); scanf("%d",&n); printf("请输入物品的重量和单位重量价值:n")