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

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

  1. 1、本文档共7页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
分支界限法解0-1背包问题实验报告

实验5 分支界限法解0-1背包问题 一 、实验要求 要求用分支界限法求解0-1背包问题; 要求交互输入背包容量,物品重量数组,物品价值数组; 要求显示结果。 二 、实验仪器和软件平台 仪器 :带usb接口微机 软件平台:WIN-XP + VC++6.0 三 、源程序 #include stdafx.h #includeiostream #includecstdio #includeconio.h #includeiomanip 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;in;i++) { minl=1.0*p[i]/w[i]; k=0; for(j=1;j=n-i;j++) { if(minl1.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;in;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

文档评论(0)

yan698698 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档