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

《分支限界求装载问题实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分支限界附件王举1021附件：1.用c++代码实现#include#includeusingnamespacestd;templateclassQueue{queueworker;public:voidAdd(Typeelement){worker.push(element);}boolIsEmpty(){returnworker.empty();}voidDelete(Type&get){get=worker.front();worker.pop();}};temp

2、lateclassQNode{private:QNode*parent;boolLChild;Typeweight;friendvoidEnQueue(Queue*>&,Type,int,int,Type,QNode*,QNode*&,int*,bool);friendTypeMaxLoading(Type*,Type,int,int*);};templatevoidEnQueue(Queue*>&Q,Typewt,in

3、ti,intn,Typebestw,QNode*E,QNode*&bestE,intbestx[],boolch){//将活结点加入到活结点队列Q中if(i==n){//可行结点if(wt==bestw){//当前最优载重量bestE=E;bestx[n]=ch;}分支限界附件王举1021return;}//非叶子结点QNode*b;b=newQNode;b->weight=wt;b->parent=E;b->LChild=ch;Q.Add(b);}template

4、TypeMaxLoading(Typew[],Typec,intn,intbestx[]){//队列式分支限界法，返回最优载重量，bestx返回最优解//初始化Queue*>Q;//活结点队列Q.Add(0);//同层结点尾部标志inti=1;//当前扩展结点所处的层TypeEw=0,//扩展结点所相应的载重量bestw=0,//当前最优载重量r=0;//剩余集装箱重量for(intj=2;j<=n;j++)r+=w[j];QNode*E=0,//当前扩展结点*bestE;//当前最优扩展结点//搜

5、索子集空间树while(true){//检查左孩子结点Typewt=Ew+w[i];if(wt<=c){//可行结点if(wt>bestw)bestw=wt;EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);}//检查右孩子结点if(Ew+r>bestw)EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);Q.Delete(E);//取下一个扩展结点if(!E){//同层结点尾部if(Q.IsEmpty())break;分支限界附件王举10

6、21Q.Add(0);//同层结点尾部标志Q.Delete(E);//取下一扩展结点i++;//进入下一层r-=w[i];//剩余集装箱重量}Ew=E->weight;//新扩展结点所相应的载重量}//构造当前最优解for(j=n-1;j>0;j--){bestx[j]=bestE->LChild;bestE=bestE->parent;}returnbestw;}voidmain(){int*p,n,c,*key,bestkey;cout<<"请输入集装箱个数："<>n;cout<<"在输入船的最大载

7、重量"<>c;cout<<"输入这"<>p[i];}/*p[4]=23;p[1]=32;p[2]=33;p[3]=44;*/bestkey=MaxLoading(p,c,n,key);cout<<"最优解值为："<

8、<=n;i++)if(key[i]>0)cout<