0-1背包问题分支限界法.doc

分支限界法——01背包问题
12软工028胡梦颖

问题描述
0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

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

三．源代码
#include<stdio.h>
#include<malloc.h>
#defineMaxSize100//结点数的最大值
typedefstructQNode
{
floatweight;
floatvalue;
intceng;
structQNode*parent;
boolleftChild;
}QNode,*qnode;
typedefstruct
{
qnodeQ[MaxSize];
intfront,rear;
}SqQueue;//存放结点的队列
SqQueuesq;
floatbestv=0;//最优解
intn=0;//实际物品数
floatw[MaxSize];//物品的重量
floatv[MaxSize];//物品的价值
intbestx[MaxSize];//存放最优解
qnodebestE;
voidInitQueue(SqQueue&sq)//队列初始化
{
sq.front=1;
sq.rear=1;
}
boolQueueEmpty(SqQueuesq)//队列是否为空
{
if(sq.front==sq.rear)
returntrue;
else
returnfalse;
}
voidEnQueue(SqQueue&sq,qnodeb)//入队
{
if(sq.front==(sq.rear+1)%MaxSize)
{
printf("队列已满!");
return;
}
sq.Q[sq.rear]=b;
sq.rear=(sq.rear+1)%MaxSize;
}qnodeDeQueue(SqQueue&sq)//出队
{
qnodee;
if(sq.front==sq.rear)
{
printf("队列已空!");
return0;
}
e=sq.Q[sq.front];
sq.front=(sq.front+1)%MaxSize;
returne;
}
voidEnQueue1(floatwt,floatvt,inti,QNode*parent,boolleftchild)
{
qnodeb;
if(i==n)//可行叶子结点
{if(vt==bestv)

{bestE=parent;
bestx[n]=(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);
}
voidmaxLoading(floatw[],floatv[],intc)
{
floatwt=0;
floatvt=0;
inti=1;//当前的扩展结点所在的层
floatew=0;//扩展节点所相应的当前载重量
floatev=0;//扩展结点所相应的价值
qnodee=NULL;
qnodet=NULL;
InitQueue(sq);
EnQueue(sq,t);//空标志进队列
while(!QueueEmpty(sq))