分支限界求装载问题实验报告

分支限界附件 王举 1021附件：1. 用c+代码实现#include #include using namespace std;template class Queuequeue worker;public:void Add(Type element)worker.push(element);bool IsEmpty()return worker.empty();void Delete(Type & get)get=worker.front();worker.pop(); ;templateclass QNodeprivate:QNode *parent;bool LChild;Type weight;friend void EnQueue(QueueQNode *&,Type,int,int,Type,QNode*,QNode*&,int*,bool);friend Type MaxLoading(Type*,Type,int,int*);templatevoid EnQueue(QueueQNode*&Q,Type wt, int i,int n,Type bestw,QNode *E, QNode*&bestE,int bestx,bool ch)/将活结点加入到活结点队列Q中if(i=n) /可行结点if (wt=bestw) /当前最优载重量bestE=E;bestxn=ch;return; /非叶子结点QNode*b;b=new QNode;b-weight=wt;b-parent=E;b-LChild=ch;Q.Add(b);templateType MaxLoading(Type w,Type c,int n,int bestx)/队列式分支限界法，返回最优载重量， bestx返回最优解/初始化 QueueQNode*Q;/活结点队列 Q.Add(0);/同层结点尾部标志 int i=1;/当前扩展结点所处的层 Type Ew=0,/扩展结点所相应的载重量 bestw=0,/当前最优载重量 r=0;/剩余集装箱重量 for (int j=2;j=n;j+)r+=wj; QNode *E= 0,/当前扩展结点 *bestE;/当前最优扩展结点 /搜索子集空间树 while (true) /检查左孩子结点 Type wt=Ew+wi; if (wtbestw) bestw=wt; EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true); /检查右孩子结点 if(Ew+rbestw)EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false); Q.Delete(E);/取下一个扩展结点 if(!E)/同层结点尾部 if(Q.IsEmpty()break; Q.Add(0);/同层结点尾部标志 Q.Delete(E);/取下一扩展结点 i+;/进入下一层 r-=wi;/剩余集装箱重量 Ew=E-weight;/新扩展结点所相应的载重量 /构造当前最优解 for(j=n-1;j0;j-) bestxj=bestE-LChild; bestE=bestE-parent; return bestw;void main() int *p,n,c,*key,bestkey;cout请输入集装箱个数：endln;cout在输入船的最大载重量endlc;cout输入这n个集装箱重量endl;/*n=4;c=60;*/p=new intn+1;key=new intn+1;for (int i=1;i=n;i+)coutwipi;/*p4=23;p1=32;p2=33;p3=44;*/bestke