装载问题5种解决方案.doc
《装载问题5种解决方案.doc》由会员分享,可在线阅读,更多相关《装载问题5种解决方案.doc(33页珍藏版)》请在咨信网上搜索。
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测试截图35II一问题定义有一批共有 n 个集装箱要装上两艘载重量分别为 c1
2、 和 c2 的轮船,其中集装箱 i 的重量为 wi, 且重量之和小于(c1 + c2)。装载问题要求确定是否存在一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有,找出一种装载方案。二解决方案1优先队列式分支限界法求解1.1算法分析活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中,一旦有一个叶结点成为当前扩展结点,则可以断言该叶结点所相应的解即为最优解.此时
3、可终止算法。1.2代码1。2-1/MaxHeap.htemplateclassTclassMaxHeappublic:MaxHeap(intMaxHeapSize=10);MaxHeap()deleteheap;intSize()constreturnCurrentSize;TMax()/查找if(CurrentSize=0)throwOutOfBounds();returnheap1;MaxHeapTInsert(constT&x);/增MaxHeapT&DeleteMax(Tx);/删voidInitialize(Ta,intsize,intArraySize);private:intCu
4、rrentSize,MaxSize;T*heap;/elementarray;templateclassTMaxHeap::MaxHeap(intMaxHeapSize)/Maxheapconstructor。MaxSize=MaxHeapSize;heap=newTMaxSize+1;CurrentSize=0;templateclassTMaxHeapMaxHeap:Insert(constT&x)/Insertxintothemaxheap.if(CurrentSize=MaxSize)cout”nospace!MaxHeapTMaxHeap:DeleteMax(Tx)/Setxtoma
5、xelementanddeletemaxelementfromheap./checkifheapisemptyif(CurrentSize=0)cout”Emptyheap!”endl;returnthis;x=heap1;/删除最大元素/重整堆Ty=heapCurrentSize-;/取最后一个节点,从根开始重整/findplaceforystartingatrootinti=1,/currentnodeofheapci=2;/childofiwhile(ci=CurrentSize)/使ci指向i的两个孩子中较大者if(ciCurrentSize&heapciheapci+1)ci+;/y
6、的值大于等于孩子节点吗?if(y=heapci)break;/是,i就是y的正确位置,退出/否,需要继续向下,重整堆heapi=heapci;/大于父节点的孩子节点上升i=ci;/向下一层,继续搜索正确位置ci=2;heapi=y;returnthis;templateclassTvoidMaxHeapT::Initialize(Ta,intsize,intArraySize)/Initializemaxheaptoarraya.deleteheap;heap=a;CurrentSize=size;MaxSize=ArraySize;/从最后一个内部节点开始,一直到根,对每个子树进行堆重整fo
7、r(inti=CurrentSize/2;i=1;i-)Ty=heapi;/子树根节点元素/findplacetoputyintc=2*i;/parentofcistarget/locationforywhile(c=CurrentSize)/heapcshouldbelargersiblingif(cCurrentSize&heapcheapc+1)c+;/canweputyinheapc/2?if(y=heapc)break;/yes/noheapc/2=heapc;/movechildupc=2;/movedownalevelheapc/2=y;1.22/6d32。cpp/装载问题优先队
8、列式分支限界法求解#includestdafx。hincludeMaxHeap.h”includeusingnamespacestd;constintN=4;classbbnode;templateclassTypeclassHeapNodetemplatefriendvoidAddLiveNode(MaxHeapHeapNodeH,bbnode*E,Typewt,boolch,intlev);templatefriendTypeMaxLoading(Typew,Typec,intn,intbestx);public:operatorType()constreturnuweight;priva
9、te:bbnodeptr;/指向活节点在子集树中相应节点的指针Typeuweight;/活节点优先级(上界)intlevel;/活节点在子集树中所处的层序号;classbbnodetemplatefriendvoidAddLiveNode(MaxHeap&H,bbnode*E,Typewt,boolch,intlev);templateclassTypefriendTypeMaxLoading(Typew,Typec,intn,intbestx);friendclassAdjacencyGraph;private:bbnodeparent;/指向父节点的指针boolLChild;/左儿子节点标
10、识;templateclassTypevoidAddLiveNode(MaxHeapH,bbnode*E,Typewt,boolch,intlev);templateclassTypeTypeMaxLoading(Typew,Typec,intn,intbestx);intmain()floatc=70;floatw=0,20,10,26,15;/下标从1开始intxN+1;floatbestw;cout”轮船载重为:cendl;cout待装物品的重量分别为:”endl;for(inti=1;i=N;i+)coutwi;coutendl;bestw=MaxLoading(w,c,N,x);co
11、ut”分支限界选择结果为:endl;for(inti=1;i=4;i+)coutxi”;coutendl;cout”最优装载重量为:bestwendl;return0;/将活节点加入到表示活节点优先队列的最大堆H中templateclassTypevoidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,Typewt,boolch,intlev)bbnodeb=newbbnode;bparent=E;b-LChild=ch;HeapNodeN;N.uweight=wt;N。level=lev;N.ptr=b;H。Insert(N);/优先队列式分支限界法,返回最优载
12、重量,bestx返回最优解templateTypeMaxLoading(Typew,Typec,intn,intbestx)/定义最大的容量为1000MaxHeap0;j)rj=rj+1+wj+1;/初始化inti=1;/当前扩展节点所处的层bbnodeE=0;/当前扩展节点TypeEw=0;/扩展节点所相应的载重量/搜索子集空间树while(i!=n+1)/非叶子节点/检查当前扩展节点的儿子节点if(Ew+wi=c)AddLiveNode(H,E,Ew+wi+ri,true,i+1);/右儿子节点AddLiveNode(H,E,Ew+ri,false,i+1);/取下一扩展节点HeapNod
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 装载 问题 解决方案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。