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

实验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