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

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