当前位置:首页 >> 计算机软件及应用 >>

用回溯法和队列式分支限界算法求解0-1背包问题


华北水利水电学院
2009 ~2010 学年 第 班级: 一、 实验题目: 200915326

数据结构与算法分析 实验报告
1 学期 2009 级 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 "stdafx.h" #include <iostream.h> #define MaxSize 100 int limitw; int maxwv=0; int int int int maxw; n; option[MaxSize]; op[MaxSize];

//最多物品数 //限制的总重量 //存放最优解的总价值 //实际物品数 // 存放最终解 //存放临时解

struct { int weight; int value; }a[MaxSize]; void Knap( int i, int tw, int tv) { int j; if(i>=n) {

//存放物品数组 //考虑第 i 个物品

//找到一个叶子结点 //找到一个满足条件地更优解,保存它

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); } } 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; Knap(0,0,0); cout<<"最佳装填方案是:"<<endl; for(j=0;j<n;j++) if(option[j]==1) cout<<"第"<<j+1<<"种物品"<<endl; cout<<"总重量="<<maxw<<",总价值="<<maxwv<<endl; return 0; }

//限制重量不超过 30

回溯法测试结果: 测试数据:物品一:重量:16,价格:45; 物品二:重量:15,价格:25; 物品三:重量:15,价格:25;









B:分支限界法: #include <stdio.h> #include<malloc.h> #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)) EnQueue(sq,NULL); e=DeQueue(sq); i++; } ew=e->weight; ev=e->value; } 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++)
第 页 共 页

// 左儿子结点进队列

//右儿子总是可行; // 取下一扩展结点

break; // 同层结点尾部标志 // 取下一扩展结点

//更新当前扩展结点的值

//构造最优解

{ if(bestx[k]==1) printf("\n 物品%d:重量:%.1f,价值:%.1f\n",k,w[k],v[k]); } printf("\n"); printf("最优价值为:%.1f\n\n",bestv);

} void main() { int c; float ewv[MaxSize]; printf(" //////////////////// 0-1 背包问题分枝限界法 /////////////////////\n\n"); printf("请输入物品的数量:\n"); scanf("%d",&n); printf("请输入背包的最大承重量:\n"); scanf("%d",&c); printf("\n 请输入物品的重量和单位重量价值:\n\n"); for(int i=1;i<=n;i++) { printf("物品%d:",i); scanf("%f%f",&w[i],&ewv[i]); v[i]=w[i]*ewv[i]; printf("\n"); } maxLoading(w, v, c); }

分支限界法测试结果:
第 页 共 页

五、小结(包括收获、心得体会、存在的问题及解决问题的方法、建议等)
注:内容一律使用宋体五号字,单倍行间距,不得少于 100 字。 1 通过这次试验是我对数据结构有了进一步的了解,可以通过算法解决实际问题(背包问题) 。 2 在用分支限界法实现问题时遇到了有关队列的问题,通过上网搜索,问老师得以解决。 3 在老师有计划的指导安排下,我的编程能力突飞猛进,在此,对老师深表感谢! !










相关文章:
用回溯法和队列式分支限界算法求解0-1背包问题.doc
用回溯法和队列式分支限界算法求解0-1背包问题 - 华北水利水电学院 2009
回溯法和分支限界法解决0-1背包题要点.doc
0-1 背包问题计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述:...(N); } //优先队列式分支限界法,返回最大价值,bestx 返回最优解 template<...
回溯法和分支限界法解决0-1背包题(精).doc
0-1 背包问题 计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述...优先队列式 分支限界法:处理法则:价值大者优先。{}>{A}>{B,C}>{C...
优先队列式分支限界法求解0-1背包问题_图文.doc
优先队列式分支限界法求解0-1背包问题 - 算法分析设计实验报告 第 7 次实
分别用回溯法和分支限界法求解0-1背包问题.doc
分别用回溯法和分支限界法求解0-1背包问题_IT/计算机_专业资料。分别用回溯法和...(SqQueue &sq ) //队列初始化 { sq.front=1; sq.rear=1; } bool Queue...
0_1背包问题的多种解法.doc
不允许只取一部分) 二、 算法分析根据问题描述,可以...(b)用回溯法求解 0-1 背包问题的过程 递归法:在...限界分支法:在解 0-1 背包问题的优先队列式界限...
分支界限法解0-1背包问题实验报告.doc
要求用分支界限法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,...用回溯法和队列式分支限... 8页 2下载券 喜欢此文档的还喜欢 算法...
实验4 用分支限界法实现0-1背包问题.doc
要求:使用优先队列式分支限界法算法编程,求解 0-1 背包问题 三.程序列表 #...分别用回溯法和分支限界... 8页 2下载券 利用分枝界限法求解0-1背... ...
第五组分支限界法(0-1背包问题).doc
问题分支限界法 ) 2) 进一步掌握分支限界法的基本思想和算法设计方法; ) 进一步...用分支限界求解0-1背包问... 6页 1下载券 用回溯法和队列式分支限.....
0_1背包问题的多种解法.doc
不允许只取一部分) 二、 算法分析根据问题描述,可以...(b)用回溯法求解 0-1 背包问题的过程 递归法:在...限界分支法:在解 0-1 背包问题的优先队列式界限...
第5章-3 分支限界算法设计基本方法_图文.ppt
掌握分支限界法算法框架 (1)队列式(FIFO)分支...(1) 0-1背包问题; (2)装载问题;南京信息工程...分支限界法与回溯法的区别:(1)求解目标:回溯法的...
算法分析与设计基础知识习题.doc
3.回溯法解旅行售货员问题时的解空间树是( A、...0/1 背包问题 6.动态规划算法的基本要素为(C) A...队列式(FIFO)分支限界法与优先队列式分支限界法; ...
解0-1背包问题的算法比较.pdf
有最优解性 质,故 0-1 背包问题满足动态规划、回溯法和分支限界法求解条件...最常 见的两种: (1)队列式(FIFO)分支限界法 按照队列先进先出(FIFO)原则...
《算法分析与设计》期末考试复习题纲(完整版)_图文.doc
A.LCS 问题 B.批处理作业问题 C.0-1 背包问题 D.哈夫曼编码问题 用回溯法...(nlogn) D.O(n),O(nlogn) 优先队列式分支限界法选取扩展结点的原则是( C ...
《计算机算法设计与分析》PPT第六章 分支限界法(4).ppt
回溯法、分支限界法解0-... 15页 1下载券 算法...? 掌握分支限界法的算法框架 (1)队列式(FIFO)分支...优先队列式分支限界法求解0-1背包问题 × 25 ? ...
算法设计与分析复习题目及答案.doc
N 皇后问题,0/1 背包问题 是贪心算法的基本要素的...( 最小堆 ) 优先队列式分支限界法选取扩展结点的...用回溯法解问题时, 应明确定义问题的解空间,问题的...
算法设计与分析_第6章_分支限界法_图文.pdf
? 理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架 ? ? 队列式(FIFO)分支限界法 优先队列式分支限界法 0-1背包问题 算法设计分析第 6章 分支限界法...
算法第6章_图文.ppt
? 掌握分支限界法的算法框架 (1)队列式(FIFO)分支...4 ? ? 分支限界法与回溯法的区别(1)求解目标不...优先队列式分支限界法求解0-1背包问题 × 25 ? ...
分支限界法解01背包问题.doc
回溯法, 也是在问题的解空间上搜索问题解的算法...优 先队列式分支限界法搜索策略: ? 对每一活结点...分支限界求解0-1背包问... 6页 免费 01...
分支限界法_图文.ppt
掌握分支限界法算法框架 队列式(FIFO)分支限界...0-1背包问题 2015-4-6 算法设计与分析 2 6.1 ...分支限界法与回溯法的不同求解目标: 回溯法的...
更多相关标签: