分别用回溯法和分支限界法求解0-1背包问题.doc

第页共页
实验题目：
分别用回溯法和分支限界法求解0-1背包问题
实验内容：
0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。
程序源代码：
A:回溯法：
//bag1.cpp:Definestheentrypointfortheconsoleapplication.
//

#include"stdafx.h"
#include<iostream.h>
#defineMaxSize100//最多物品数
intlimitw;//限制的总重量
intmaxwv=0;//存放最优解的总价值
intmaxw;
intn;//实际物品数
intoption[MaxSize];//存放最终解
intop[MaxSize];//存放临时解
struct{
intweight;
intvalue;
}a[MaxSize];//存放物品数组
voidKnap(inti,inttw,inttv)//考虑第i个物品
{
intj;
if(i>=n)//找到一个叶子结点
{
if(tw<=limitw&&tv>maxwv)//找到一个满足条件地更优解，保存它
{
maxwv=tv;maxw=tw;
for(j=0;j<n;j++)option[j]=op[j];
}
}
else
{
op[i]=1;//选取第I个物品
Knap(i+1,tw+a[i].weight,tv+a[i].value);
op[i]=0;//不选取第I个物品，回溯
Knap(i+1,tw,tv);
}

}

intmain(intargc,char*argv[])
{
intj;
n=3;//3物品
a[0].weight=16;a[0].value=45;
a[1].weight=15;a[1].value=25;
a[2].weight=15;a[2].value=25;
//a[3].weight=1;a[3].value=1;
limitw=30;//限制重量不超过30
Knap(0,0,0);
cout<<"最佳装填方案是："<<endl;
for(j=0;j<n;j++)
if(option[j]==1)
cout<<"第"<<j+1<<"种物品"<<endl;
cout<<"总重量＝"<<maxw<<",总价值＝"<<maxwv<<endl;
return0;
}
回溯法测试结果：
测试数据：物品一：重量：16，价格：30；
物品二：重量：15，价格：15；
物品三：重量：14，价格：25；

B：分支限界法：
#include<stdio.h>
#include<malloc.h>
#defineMaxSize100//最多结点数
typedefstructQNode
{
floatweight;
floatvalue;
int ceng;
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=s