《装载问题5种项目解决方案》由会员分享，可在线阅读，更多相关《装载问题5种项目解决方案（46页珍藏版）》请在金锄头文库上搜索。
1、. . . . .算法分析与设计 2016/2017(2) 实验题目 装载问题5种解法 学生姓名 学生学号 学生班级 任课教师 提交日期2017 计算机科学与技术学目录一问题定义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代码274.3测试截图315贪心算法315.1算法分析315.2代码315.3测试截图35 . 专业学习资料 .一问题定义有一批共有 n 个集装箱要
2、装上两艘载重量分别为 c1 和 c2 的轮船，其中集装箱 i 的重量为 wi, 且重量之和小于(c1 + c2)。装载问题要求确定是否存在一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有，找出一种装载方案。二解决方案1优先队列式分支限界法求解1.1算法分析活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点
3、所相应的解即为最优解。此时可终止算法。1.2代码1.2-1/MaxHeap.htemplateclassMaxHeappublic:MaxHeap(intMaxHeapSize=10);MaxHeap()deleteheap;intSize()constreturnCurrentSize;TMax()/查找if(CurrentSize=0)throwOutOfBounds();returnheap1;MaxHeap&Insert(constT&x);/增MaxHeap&DeleteMax(T&x);/删voidInitialize(Ta,intsize,intArraySize);privat
4、e:intCurrentSize,MaxSize;T*heap;/elementarray;templateMaxHeap:MaxHeap(intMaxHeapSize)/Maxheapconstructor.MaxSize=MaxHeapSize;heap=newTMaxSize+1;CurrentSize=0;templateMaxHeap&MaxHeap:Insert(constT&x)/Insertxintothemaxheap.if(CurrentSize=MaxSize)coutnospace!heapi/2)/i不是根节点，且其值大于父节点的值，需要继续调整heapi=heapi
5、/2;/父节点下降i/=2;/继续向上，搜寻正确位置heapi=x;return*this;templateMaxHeap&MaxHeap:DeleteMax(T&x)/Setxtomaxelementanddeletemaxelementfromheap./checkifheapisemptyif(CurrentSize=0)coutEmptyheap!endl;return*this;x=heap1;/删除最大元素/重整堆Ty=heapCurrentSize-;/取最后一个节点，从根开始重整/findplaceforystartingatrootinti=1,/currentnodeofh
6、eapci=2;/childofiwhile(ci=CurrentSize)/使ci指向i的两个孩子中较大者if(ciCurrentSize&heapci=heapci)break;/是，i就是y的正确位置，退出/否，需要继续向下，重整堆heapi=heapci;/大于父节点的孩子节点上升i=ci;/向下一层，继续搜索正确位置ci*=2;heapi=y;return*this;templatevoidMaxHeap:Initialize(Ta,intsize,intArraySize)/Initializemaxheaptoarraya.deleteheap;heap=a;CurrentSiz
7、e=size;MaxSize=ArraySize;/从最后一个内部节点开始，一直到根，对每个子树进行堆重整for(inti=CurrentSize/2;i=1;i-)Ty=heapi;/子树根节点元素/findplacetoputyintc=2*i;/parentofcistarget/locationforywhile(c=CurrentSize)/heapcshouldbelargersiblingif(cCurrentSize&heapc=heapc)break;/yes/noheapc/2=heapc;/movechildupc*=2;/movedownalevelheapc/2=y;
8、1.2-2/6d3-2.cpp/装载问题优先队列式分支限界法求解#includestdafx.h#includeMaxHeap.h#includeusingnamespacestd;constintN=4;classbbnode;templateclassHeapNodetemplatefriendvoidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,Typewt,boolch,intlev);templatefriendTypeMaxLoading(Typew,Typec,intn,intbestx);public:operatorType()constreturnuweight;private:bbnode*ptr;/指向活节点在子集树中相应节点的指针Ty
