第五组分支限界法(0-1背包问题)

0-1背包问题的分支限界法与实现

任务分配 成员1 成员2 张藤 金洲 成绩 成绩 综合分数 一、 设计目的

1） 掌握0-1背包问题的分支限界法；

2） 进一步掌握分支限界法的基本思想和算法设计方法；

二、 设计内容

1． 任务描述

1） 算法简介

分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

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

式称为分支限界法。人们已经用分支限界法解决了大量离散最优化的问题。

2） 0-1背包问题简介

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。 3） 设计任务简介

对于分支限界类似的问题。首先，要能理解该问题运用到的分支限界的概念；其次，根据分支限界相关的基本思想，找出相应的数学公式；最后，进行程序的设计和编写。

利用分支限界的基本思想和计算步骤，有助于我们解决生活中遇到的各种数学问题。

4） 问题分析

在解0-1背包问题的优先队列式分支限界法中，活结点优先队列中结点元素N的优先级由该结点的上界函数Bound计算出的值uprofit给出。子集树中以结点N为根的子树中任一结点的价值不超过N.profit。可用一个最大堆来实现活结点优先队列。堆中元素类型为HeapNode，其私有成员有

uprofit,profit,weight和level。对于任意活结点N，N.weight是结点N所相应的重量；N.profit是N所相应的价值；N.uprofit是结点N的价值上界，最大堆以这个值作为优先级。子集空间树中结点类型为bbnode。

0-1背包问题的表示方案

2． 递推过程的抽象描述

本设计采用前向或后向递推公式。用自然语言、伪程序设计语言或流程图等形式针对0-1背包问题的求解（抽象地）描述递推过程……

3． 主要数据类型与变量 float weight;//物品重量

float value;//物品价值 int ceng;//

struct QNode *parent;//子结点 bool leftChild;//左儿子结点

4． 算法或程序模块

void maxLoading(float w[],float v[],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+w[i]; vt=ev+v[i]; if (wt <= c) {

if(vt>bestv) bestv=vt;

EnQueue1(wt,vt,i,e,true); // 左儿子结点进队列 }

EnQueue1(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(\"最优价值为：%.0f\\n\\n\ printf(\"最优取法为：\\n\");

for( int j=n-1;j>0;j--) //构造最优解 {

bestx[j]=(bestE->leftChild?1:0); bestE=bestE->parent; }

for(int k=1;k<=n;k++) {

if(bestx[k]==1)

printf(\"\\n物品%d:重量：%.0f，价值：%.0f\\n\\n\}

三、 测试

1． 方案

描述测试方案、测试模块、测试数据实例（文字数据、图或表等形式）……

2． 结果

四、 总结与讨论

通过构造函数，利用回溯思想编写代码，利用回溯的基本思想和计算步骤，有助于我们解决生活中遇到的各种数学问题。

附：程序模块的源代码

#include #include

#define MaxSize 100 //最多结点数 typedef struct QNode {

float weight; float value; int ceng;

struct QNode *parent; bool leftChild;

}QNode,*qnode; //存放每个结点 typedef struct {

qnode Q[MaxSize]; int front,rear;

}SqQueue; //存放结点的队列 SqQueue sq;

float bestv=0; //最优解

int n=0; //实际物品数 float w[MaxSize]; //物品的重量 float v[MaxSize]; //物品的价值 int bestx[MaxSize]; // 存放最优解 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.front==(sq.rear+1)%MaxSize) {

printf(\"队列已满!\"); return ; }

sq.Q[sq.rear]=b;

sq.rear=(sq.rear+1)%MaxSize; }

qnode DeQueue(SqQueue &sq)//出队 {

qnode e;

if(sq.front==sq.rear) {

printf(\"队列已空!\"); return 0; }

e=sq.Q[sq.front];

sq.front=(sq.front+1)%MaxSize; return e; }

void EnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild) {

qnode b;

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); }

void maxLoading(float w[],float v[],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+w[i]; vt=ev+v[i]; if (wt <= c) {

if(vt>bestv) bestv=vt;

EnQueue1(wt,vt,i,e,true); // 左儿子结点进队列 }

EnQueue1(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(\"最优价值为：%.0f\\n\\n\ printf(\"最优取法为：\\n\");

for( int j=n-1;j>0;j--) //构造最优解 {

bestx[j]=(bestE->leftChild?1:0); bestE=bestE->parent; }

for(int k=1;k<=n;k++) {

if(bestx[k]==1)

printf(\"\\n物品%d:重量：%.0f，价值：%.0f\\n\\n\ } }

void main() {

int c;

float ewv[MaxSize];

printf(\" //////////////////// 0-1背包问题分枝限界法 /////////////////////\\n\\n\"); printf(\"请输入物品的数量：\\n\"); scanf(\"%d\

printf(\"请输入背包的最大承重量：\\n\"); scanf(\"%d\

printf(\"\\n请输入物品的价值和重量:\\n\\n\"); for(int i=1;i<=n;i++) {

printf(\"物品%d:\

scanf(\"%f%f\ v[i]=ewv[i]; printf(\"\\n\");

}

maxLoading(w, v, c); }

参考：http://wenku.baidu.com/view/39c3704ce51bcf847c27.html