计算机算法设计与分析实验报告

15

实验五：分支限界法求解0-1背包问题

一、 实验目的

分支限界法求解0-1背包问题

二、 实验内容

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

三、 实验代码

#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; //最优解

16

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 }

void EnQueue(SqQueue &sq,qnode b)//入队 {

if(sq.front==(sq.rear+1)%MaxSize) { }

sq.Q[sq.rear]=b;

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

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

17

return false;

printf(\队列已满!\return ;

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, 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;

18

bool

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); // 同层结点尾部标志

19