分支限界法实验最优装载问题

算法分析与设计实验报告 第 八 次附加实验 姓名 学号 班级 时间 12.26上午 地点 工训楼309 实验名称 分支限界法实验(最优装载问题) 实验目的 1. 掌握分支限界法求解问题的思想 学会利用队列求解最优装载问题 2. 实验原理 问题描述： 有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 则采用下面的策略可得到最优装载方如果一个给定装载问题有解，容易证明： 案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。 实验步骤 ）在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结（1 点；）如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点（2个儿子结点都产生后，当前扩展结点。2队列中(右儿子结点一定是可行结点)被舍弃； ）活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层（3 结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空；时，再判断当前队列是否为空。如果队列非空，则将-14）当取出的元素是（ -1尾部标记加入活结点队列，算法开始处理下一层的活结点。 关键代码 void Maxloading(int w[],int c,int n,int bestx[]) //其中w[]为重量数组| { // c为船的总载重量,n为节点数 //初始化 queue Q; //活节点队列 Q.push(0); //将第一个节点加入队列中，并用0表示同层节点的尾部标志 当前扩展节点的层数，此时为// i=1; int int Ew=0; //扩展节点相应的载重量 int bestw=0; //当前最优载重量 int r=0; //剩余集装箱的重量 for(int j=2;j=bestw) Enqueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);//将右节点加入队列 E=Q.front(); //取出当前扩展节点 Q.pop(); if(!E) //到达同层的最末，此时需要更新剩余装箱载重量 { if(Q.empty()) break; //此时队列为空 Q.push(0); //加入0，表示该层结束 E=Q.front(); Q.pop(); i++; //进入下一层 r-=w[i];//更新剩余集装箱的值 } Ew=E->weight; //新扩展的节点对应的载重量 } //构造当前最优解 for(int j=n-1;j>0;j--) { bestx[j]=bestE->LChild; bestE=bestE->parent; } coutweight=wt; b->parent=E; b->LChild=ch; Q.push(b); } void Maxloading(int w[],int c,int n,int bestx[]) //其中w[]为重量