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

华北水利水电学院 数据结构与算法分析 实验报告

2009 ～2010 学年 第 1 学期 2009 级 计算机 专业

班级： 200915326 学号： 200915326 姓名： 郜莉洁

一、 实验题目：

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

二、 实验内容：

0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

三、 程序源代码： A:回溯法：

// bag1.cpp : Defines the entry point for the console application. //

#include \

#include

#define MaxSize 100 //最多物品数 int limitw; //限制的总重量

int maxwv=0; //存放最优解的总价值 int maxw;

int n; //实际物品数

int option[MaxSize]; // 存放最终解 int op[MaxSize]; //存放临时解 struct { int weight;

int value;

}a[MaxSize]; //存放物品数组

void Knap( int i, int tw, int tv) //考虑第i个物品

{ int j;

if(i>=n) //找到一个叶子结点 { if (tw<=limitw && tv>maxwv) //找到一个满足条件地更优解，保存它 {

maxwv=tv; maxw=tw;

for(j=0;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); }

int main(int argc, char* argv[]) {

int j;

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<<\最佳装填方案是：\

for(j=0;j

return 0; }

回溯法测试结果：

测试数据：物品一：重量：16，价格：45；

物品二：重量：15，价格：25；

物品三：重量：15，价格：25；

第 页 共 页

B：分支限界法： #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) //队列是否为空

第 页 共页

{ }

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

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

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

第 页 共 页

if(sq.front==sq.rear)

return true;

else

return false;

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

sq.Q[sq.rear]=b;

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

printf(\队列已满!\return ;

qnode e;

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

e=sq.Q[sq.front];

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

printf(\队列已空!\return 0;

{ }

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

第 页 共 页

qnode b;

if (i==n) //可行叶子结点 { }

b=(qnode)malloc(sizeof(QNode)); //非叶子结点 b->weight=wt; b->value=vt; b->ceng=i; b->parent=parent; b->leftChild=leftchild; EnQueue(sq,b);

if (vt==bestv) { } return;

bestE=parent;

bestx[n]=(leftchild)?1:0;

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库分别用回溯法和分支限界法求解0-1背包问题在线全文阅读。