15
实验五：分支限界法求解0-1背包问题
一、 实验目的
分支限界法求解0-1背包问题
二、 实验内容
0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。
三、 实验代码
#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
计算机算法设计与分析实验报告
