当前位置:首页 >> 数学 >>

分支界限法解0-1背包问题实验报告


实验 5
一 、实验要求

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

1.要求用分支界限法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组; 3.要求显示结果。

二 、实验仪器和软件平台
仪器 :带 usb 接口微机 软件平台:WIN-XP + VC++6.0

三 、源程序
#include "stdafx.h" #include<iostream> #include<cstdio> #include<conio.h> #include<iomanip> using namespace std; int *x; struct node //结点表结点数据结构 { node *parent;//父结点指针 node *next; //后继结点指针 int level;//结点的层 int bag;//节点的解 int cw;//当前背包装载量 int cp;//当前背包价值 float ub; //结点的上界值 }; //类 Knap 中的数据记录解空间树中的结点信息,以减少参数传递及递归调用所需的栈空间 class Knap { private: struct node *front, //队列队首 *bestp,*first; //解结点、根结点 int *p,*w,n,c,*M;//背包价值、重量、物品数、背包容量、记录大小顺序关系 long lbestp;//背包容量最优解 public: void Sort(); Knap(int *pp,int *ww,int cc,int nn);

~Knap(); float Bound(int i,int cw,int cp);//计算上界限 node *nnoder(node *pa,int ba,float uub);//生成一个结点 ba=1 生成左节点 ba=0 生成右节 点 void addnode(node *nod);//向队列中添加活结点 void deletenode(node *nod);//将结点从队列中删除 struct node *nextnode(); //取下一个节点 void display(); //输出结果 void solvebag(); //背包问题求解 }; //按物品单位重量的价值排序 void Knap::Sort() { int i,j,k,kkl; float minl; for(i=1;i<n;i++) { minl=1.0*p[i]/w[i]; k=0; for(j=1;j<=n-i;j++) { if(minl<1.0*p[j]/w[j]) { minl=1.0*p[j]/w[j]; swap(p[k],p[j]); swap(w[k],w[j]); swap(M[k],M[j]); k=j; } } } } Knap::Knap(int *pp,int *ww,int cc,int nn) { int i; n=nn; c=cc; p=new int[n]; w=new int[n]; M=new int[n]; for(i=0;i<n;i++) { p[i]=pp[i];

w[i]=ww[i]; M[i]=i; //用 M 数组记录大小顺序关系 } front=new node[1]; front->next=NULL; lbestp=0; bestp=new node[1]; bestp=NULL; Sort(); } Knap::~Knap() { delete []first; delete []front; delete []bestp; delete []p; delete []w; }

//取上限最大结点 node *Knap::nextnode() { node *p=front->next; front->next=p->next; return(p); } //将一个新的结点插入到子集树和优先队列中 node * Knap::nnoder(struct node *pa,int ba,float uub) {//生成一个新结点 node * nodell=new(node); nodell->parent=pa; nodell->next=NULL; nodell->level=(pa->level)+1; nodell->bag=ba; nodell->ub=uub; if(ba==1) { nodell->cw=pa->cw+w[pa->level]; nodell->cp=pa->cp+p[pa->level] ; } else {

nodell->cw=pa->cw; nodell->cp=pa->cp; } return(nodell); } //将结点加入优先队列 void Knap::addnode(node *no) { node *p=front->next,*next1=front; float ub=no->ub; while(p!=NULL) { if(p->ub<ub){no->next=p;next1->next=no;break;} next1=p; p=p->next; } if(p==NULL){next1->next=no;} } // 计算结点所相应价值的上界 float Knap::Bound(int i,int cw,int cp) { int cleft=c-cw; //剩余容量 float b=(float)cp; //价值上界 //以物品单位重量价值减序装填剩余容量 while (i<n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } //装填剩余容量装满背包 if (i<n) b+=1.0*p[i]/w[i]*cleft; return b; } //计算最优值和变量值 void Knap::display() { int i; cout<<endl; cout<<"当前最优价值为:"<<lbestp<<endl; for(i=n;i>=1;i--) {

x[M[i-1]]=bestp->bag; bestp=bestp->parent; } cout<<"变量值 x = "; for(i=1;i<=n;i++) cout<<x[i-1]; cout<<endl; } //背包问题求解 void Knap::solvebag() { int i; float ubb; node *aa; //记录上限最大结点 first=new node[1]; //根结点 first->parent=NULL; first->next=NULL; first->level=0; //用 level 记录结点的层 first->cw=0; first->cp=0; first->bag=0; ubb=Bound(0,0,0); first->ub=ubb; front->next=first; while(front->next!=NULL) { aa=nextnode(); i=aa->level; //当叶子节点处的解>最优解时,更新最优解 if(i==n-1) { if(aa->cw+w[i]<=c&&(long)(aa->cp+p[i])>lbestp) { lbestp=aa->cp+p[i]; bestp=nnoder(aa,1,(float)lbestp);//将一个新的结点插入到子集树和优先队 列中 } if((long)(aa->cp)>lbestp) { lbestp=aa->cp; bestp=nnoder(aa,0,(float)lbestp); } }

//非叶子结点,递归调用 Bound 函数计算上界 if(i<n-1) { if(aa->cw+w[i]<=c&&Bound(i+1,aa->cw+w[i],aa->cp+p[i])>(float)lbestp) { ubb=Bound(i,aa->cw+w[i],aa->cp+p[i]); addnode(nnoder(aa,1,ubb));//将结点加入到优先队列中 } ubb=ubb=Bound(i,aa->cw,aa->cp); if(ubb>lbestp) addnode(nnoder(aa,0,ubb)); } } display(); } int main() { int c,n; int i=0; int *p; int *w; cout<<endl; cout<<"|***********分支限界法解 0-1 背包问题***********| "<<endl; cout<<endl; cout<<"请输入物品数量 n = "; cin>>n; cout<<endl; cout<<"请输入背包容量 C = "; cin>>c; cout<<endl; x=new int[n]; //变量值 p=new int[n]; //物品价值 w=new int[n]; //物品重量 cout<<"请分别输入这"<<n<<"个物品的重量 W:"<<endl; for(i=0;i<n;i++) cin>>w[i]; cout<<endl; cout<<"请输入这"<<n<<"个物品的价值 P:"<<endl; for(i=0;i<n;i++) cin>>p[i]; Knap knbag(p,w,c,n); knbag.solvebag(); getch();

return 0; }

四 、运行结果

五 、实验小结
回溯法的求解目标是找出解空间树中满足约束条件的所有解, 而分支限界法 的求解目标则是找出满足约束条件的一个解, 或是在满足约束条件的解中找出在 某种意义下的最优解。 回溯法以深度优先的方式搜索解空间树,而分支限界法则 以广度优先或以最小耗费优先的方式搜索解空间树。 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的 解空间树。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点 一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不 可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此 后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。


相关文章:
第五组分支限界法(0-1背包问题)
实训一 背包问题的分支限界法与实现 问题的分支限界法 0-1 背包问题分支限界法与实现任务分 配 成员 1 成员 2 张藤 金洲 成绩 综合分数 成绩 一、 设计...
分支限界法求0-1背包问题实验程序以及代码(C++)
分支限界法求0-1背包问题实验程序以及代码(C++)_理学_高等教育_教育专区。分支限界法求 背包问题实验程序以及代码 实验程序以及代码( 分支限界法求 0-1 背包问题...
回溯法、分支限界法解0-1背包问题(计算机算法设计...
回溯法、分支限界法解0-1背包问题(计算机算法设计与分析实验报告) - 报告中附有可直接运行代码和实验结果截图(西大学子)。 编程语言:java 开发工具:eclipse 3.4...
实验报告--动态规划法解0-1背包问题
实验报告--动态规划法解0-1背包问题 - 注意:红色的部分需要用自己的代码或内容进行替换。 湖南涉外经济学院 实验报告 实验课程: 算法设计与分析 实验项目: 动态...
回溯法解0-1背包问题实验报告
用回溯法算法来解0-1背包问题实验报告 实验4 一 、实验要求 回溯法解 0-...运行结果 实验小结 五 、实验小结通过该实验,我充分了解了回溯法与分支界限法的...
动态规划解决算法0-1背包问题实验报告(含源代码)
动态规划解决算法0-1背包问题实验报告(含源代码)_计算机软件及应用_IT/计算机_...2.掌握动态规划、贪心算法、回溯法、分支限界法的原理,并能够按其原理 编程实现...
0036算法笔记——【分支限界法】0-1背包问题
0036算法笔记——【分支限界法0-1背包问题_计算机软件及应用_IT/计算机_专业...cout&lt;&lt;&quot;此背包问题最优解为:&quot;&lt;&lt;endl; for(int i=1; i&lt;=n; i++) {...
0-1背包问题(分支限界法)
0-1背包问题(分支限界法) - 分支限界法——01 背包问题 12 软工 一、 问题描述 0-1 背包问题: 给定 n 种物品和一个背包。 物品 i 的重量是 Wi, 其...
优先队列式分支限界法求解0-1背包问题_图文
优先队列式分支限界法求解0-1背包问题 - 算法分析与设计实验报告 第 7 次实验 姓名 时间 实验名称 6.4 上午 学号 地点 四合院 班级 优先队列式分支限界法求解 ...
回溯法实验(0-1背包问题)
回溯法实验(0-1背包问题) - 算法分析与设计实验报告 第五 次附加实验 姓名 时间 实验名称 12.26 上午 学号 地点 班级 工训楼 309 回溯法实验(0-1 背包...
更多相关标签: