分支限界求装载问题实验报告(共4页).doc
精选优质文档-倾情为你奉上附件：1. 用c+代码实现#include <queue>#include <iostream>using namespace std;template <class Type>class Queuequeue<Type> worker;public:void Add(Type element)worker.push(element);bool IsEmpty()return worker.empty();void Delete(Type & get)get=worker.front();worker.pop(); ;template<class Type>class QNodeprivate:QNode *parent;bool LChild;Type weight;friend void EnQueue(Queue<QNode<Type> *>&,Type,int,int,Type,QNode<Type>*,QNode<Type>*&,int*,bool);friend Type MaxLoading(Type*,Type,int,int*);template<class Type>void EnQueue(Queue<QNode<Type>*>&Q,Type wt, int i,int n,Type bestw,QNode<Type> *E, QNode<Type>*&bestE,int bestx,bool ch)/将活结点加入到活结点队列Q中if(i=n) /可行结点if (wt=bestw) /当前最优载重量bestE=E;bestxn=ch;return; /非叶子结点QNode<Type>*b;b=new QNode<Type>b->weight=wt;b->parent=E;b->LChild=ch;Q.Add(b);template<class Type>Type MaxLoading(Type w,Type c,int n,int bestx)/队列式分支限界法，返回最优载重量， bestx返回最优解/初始化 Queue<QNode<Type>*>Q;/活结点队列 Q.Add(0);/同层结点尾部标志 int i=1;/当前扩展结点所处的层 Type Ew=0,/扩展结点所相应的载重量 bestw=0,/当前最优载重量 r=0;/剩余集装箱重量 for (int j=2;j<=n;j+)r+=wj; QNode<Type> *E= 0,/当前扩展结点 *bestE;/当前最优扩展结点 /搜索子集空间树 while (true) /检查左孩子结点 Type wt=Ew+wi; if (wt<=c) /可行结点 if(wt>bestw) bestw=wt; EnQueue<Type>(Q,wt,i,n,bestw,E,bestE,bestx,true); /检查右孩子结点 if(Ew+r>bestw)EnQueue<Type>(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;j>0;j-) bestxj=bestE->LChild; bestE=bestE->parent; return bestw;void main() int *p,n,c,*key,bestkey;cout<<"请输入集装箱个数："<<endl<<"n="cin>>n;cout<<"在输入船的最大载重量"<<endl<<"c=" cin>>c;cout<<"输入这"<<n<<"个集装箱重量"<<endl;/*n=4;c=60;*/p=new intn+1;key=new intn+1;for (int i=1;i<=n;i+)cout<<"w"<<i<<"="cin>>pi;/*p4=23;p1=32;p2=33;p3=44;*/bestkey=MaxLoading<int>(p,c,n,key);cout<<"最优解值为："<<bestkey<<endl;cout<<"分别是："for(i=1;i<=n;i+) if(keyi>0)cout<<pi<<'t' 2测试结果：专心-专注-专业
