装载问题5种解决方案

算法分析与设计2016/2017(2)实验题目装载问题5种解法学生姓名学生学号学生班级任课教师提交日期2017计算机科学与技术学算法分析与设计II目录一问题定义........................................................................................................................................3二解决方案........................................................................................................................................31优先队列式分支限界法求解..................................................................................................31.1算法分析......................................................................................................................31.2代码..............................................................................................................................31.3运行结果...................................................................................................................132队列式分支限界法求解.......................................................................................................132.1算法分析...................................................................................................................132.2代码...........................................................................................................................142.3测试截图...................................................................................................................223回朔法-迭代.........................................................................................................................223.1算法分析...................................................................................................................223.2代码...........................................................................................................................223.3测试截图...................................................................................................................264回朔法-递归.........................................................................................................................264.1算法分析...................................................................................................................264.2代码...........................................................................................................................264.3测试截图...................................................................................................................315贪心算法..............................................................................................................................315.1算法分析...................................................................................................................315.2代码...........................................................................................................................315.3测试截图...................................................................................................................35算法分析与设计3/35一问题定义有一批共有n个集装箱要装上两艘载重量分别为c1和c2的轮船，其中集装箱i的重量为w[i],且重量之和小于(c1+c2)。装载问题要求确定是否存在一个合理的装载方案可将这n个集装箱装上这两艘轮船。如果有，找出一种装载方案。二解决方案1优先队列式分支限界法求解1.1算法分析活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。1.2代码1.2-1////MaxHeap.htemplateclassTclassMaxHeap{public:MaxHeap(intMaxHeapSize=10);~MaxHeap(){delete[]heap;}intSize()const{returnCurrentSize;}算法分析与设计4/35TMax(){//查找if(CurrentSize==0){throwOutOfBounds();}returnheap[1];}MaxHeapT&Insert(constT&x);//增MaxHeapT&DeleteMax(T&x);//删voidInitialize(Ta[],intsize,intArraySize);private:intCurrentSize,MaxSize;T*heap;//elementarray};templateclassTMaxHeapT::MaxHeap(intMaxHeapSize){//Maxheapconstructor.MaxSize=MaxHeapSize;heap=newT[MaxSize+1];CurrentSize=0;}templateclassTMaxHeapT&MaxHeapT::Insert(constT&x){//Insertxintothemaxheap.算法分析与设计5/35if(CurrentSize==MaxSize){coutnospace!endl;return*this;}//寻找新元素x的位置//i——初始为新叶节点的位置，逐层向上，寻找最终位置inti=++CurrentSize;while(i!=1&&xheap[i/2]){//i不是根节点，且其值大于父节点的值，需要继续调整heap[i]=heap[i/2];//父节点下降i/=2;//继续向上，搜寻正确位置}heap[i]=x;return*this;}templateclassTMaxHeapT&MaxHeapT::DeleteMax(T&x){//Setxtomaxelementanddeletemaxelementfromheap.//checkifheapisemptyif(CurrentSize==0){coutEmptyheap!endl;return*this;}算法分析与设计6/35x=heap[1];//删除最大元素//重整堆Ty=heap[CurrentSize--];//取最后一个节点，从根开始重整//findplaceforystartingatrootinti=1,//currentnodeofheapci=2;//childofiwhile(ci=CurrentSize){//使ci指向i的两个孩子中较大者if(ciCurrentSize&&heap[ci]heap[ci+1]){ci++;}//y的值大于等于孩子节点吗？if(y=heap[ci]){break;//是，i就是y的正确位置，退出}//否，需要继续向下，重整堆heap[i]=heap[ci];//大于父节点的孩子节点上升i=ci;//向下一层，继续搜索正确位置ci*=2;}heap[i]=y;算法分析与设计7/35return*this;}templateclassTvoidMaxHeapT::Initialize(Ta[],intsize,intArraySize){//Initializemaxheaptoarraya.delete[]heap;heap=a;CurrentSize=size;MaxSize=ArraySize;//从最后一个内部节点开始，一直到根，对每个子树进行堆重整for(inti=CurrentSize/2;i=1;i--){Ty=heap[i];//子树根节点元素//findplacetoputyintc=2*i;//parentofcistarget//locationforywhile(c=CurrentSize){//heap[c]shouldbelargersiblingif(cCurrentSize&&heap[c]heap[c+1]){c++;}//canwe