版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、算法分析与设计实验报告学 院:信息科学与工程学院专业班级: i got7指导老师: 学 号: i got7 姓 名: 鸟宝宝a. 合并排序合并排序是分治法的应用,把需要排序的数组A1 - n,一分为二A1 -n/2和An/2+1 - n,然后在对每一个子数组递归排序,接着再把这两个子数组合并成一个有序的数组。算法描述:第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针超出序列尾,将另一序列剩下的所有元
2、素直接复制到合并序列尾关键代码:private static void Sort(int a, int left, int right) if(left=right) return; int mid = (left + right) / 2; Sort(a, left, mid); Sort(a, mid + 1, right); merge(a, left, mid, right); private static void merge(int a, int left, int mid, int right) int tmp = new inta.length; int r1 = mid +
3、1; int tIndex = left; int cIndex=left; / 逐个归并 while(left =mid & r1 = right) if (aleft = ar1) tmptIndex+ = aleft+; else tmptIndex+ = ar1+; / 将左边剩余的归并 while (left =mid) tmptIndex+ = aleft+; / 将右边剩余的归并 while ( r1 = right ) tmptIndex+ = ar1+; System.out.print( 第+(+number)+次排序: ); /从临时数组拷贝到原数组 while(cInd
4、ex=right) acIndex=tmpcIndex; /输出中间归并排序结果 System.out.print(acIndex+ ); cIndex+; System.out.println(); 运行结果截屏:算法分析:合并排序满足分治法的基本公式T(n)=2T(n/2)+f(n)其中2T(n/2)是2个子问题求解,即对两个子数组排序;而f(n)是将子问题合起来求原始问题的解的代价,即将两个有序的子数组合并为一个有序的数组。在最终的合并阶段,键值的比较的代价,在最坏的情况下是n-1 ,(比如每个数组的第i号轮流被放入数组),根据主定理,T(n)=O(nlogn)。b. 0-1背包问题问题
5、描述:在0 / 1背包问题中,需对容量为W 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品j 的重量为wj ,价值为vi 。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。有3中方法可解:动态规划法:递推式: K(w,j)=maxK(w-wj, j-1)+vj, K(w,j-1) w wj K(w,j)=K(w,j-1) w wj 初始条件: K(0,j)=0, K(w, 0)=0. 初始化条件表示把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包,得到的价值均为0。 第二个式子说明:如果第i个物品的重量大于背包的容量,则装入
6、第i个物品得到的最大价值和装入第i-1个物品得到的最大价值是相同的,即物品i不能装入背包中。 第一个式子说明:如果第i个物品的重量小于背包的容量,则会有两种情况:(1)如果把第i个物品装入背包,则背包中物品的价值就等于把前i-1个物品装入容量为iwj-的背包中的价值加上第i个物品的价值iv; (2)如果第i个物品没有装入背包,则背包中物品的价值就是等于把前i-1个物品装入容量为j的背包中所取得的价值。 显然,取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。w-wjwWj-1Kw-wj,j-1+vjKw,j-1jKw,jn目标 构建的表格:时间复杂度为:O(nw)分支限界法:1.
7、按单位价值对待处理的物品进行排序2.计算可行结点可获得的最大价值的上界 bound function(上界函数):ub=v+(W-w)(vi+1/wi+1)3. 用结点的上界值作为优先级,建立优先队列4. 按照优先队列对解空间进行搜索回溯法: 回溯法应用深度优先遍历解空间,如果按单位价值排序可以剪掉部分右边的枝,如果设置约束条件可以剪掉不是最优解的枝。 在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余物品价值总和;cp是当前价值;bestp是当前最优价值。当cp+rbestp时,可剪去右子树。 计
8、算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。 确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时,应往回溯至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索,直
9、至找到所要求的所有解或解空间中已没有活结点时为止。 贪心法:贪心法是“步步贪心”,从局部最优推进得到全局最优的近似解,所以用贪心法存在问题: 1).不能保证求得的最后解是最佳的; 2).不能用来求最大或最小解问题; 3).只能求满足某些约束条件的可行解的范围。 目标是价值最大 约束条件是装入的物品总重量不超过背包容量:wi=M( M=150) (1)根据贪心的策略,每次挑选价值最大的物品或者所占空间最小的物品装入背包,似乎不行(2)每次选取单位容量价值最大的物品,成为解题的策略。 关键代码:public void getMaxValue() PriorityQueue pq = new Pri
10、orityQueue(); /根节点 thingNode initial = new thingNode(); initial.level = -1; initial.upprofit = 26; pq.add(initial); while(!pq.isEmpty() thingNode fatherNode = pq.poll(); /叶子节点 if(fatherNode.level = n-1) if(fatherNode.value maxValue) maxValue = (int)fatherNode.value; for(int i=n-1;i=0;i-) bestWayi =
11、fatherNode.Left; fatherNode = fatherNode.father; else /判断是否加入队列 if(weightfatherNode.level+1+fatherNode.weight maxValue) pq.add(newNode); /向右节点搜索,其能够取到的价值上界通过父亲节点的上界减去本层物品的价值。 if(fatherNode.upprofit - valuefatherNode.level+1) maxValue) thingNode newNode2 = new thingNode(); newNode2.level = fatherNode
12、.level+1; newNode2.value = fatherNode.value; newNode2.weight = fatherNode.weight; newNode2.father = fatherNode; newNode2.upprofit = fatherNode.upprofit - valuefatherNode.level+1; newNode2.Left = 0; pq.add(newNode2); /用于计算该节点的最高价值上界 public double Bound(thingNode no) double maxLeft = no.value; int lef
13、tWeight = capacity - no.weight; int templevel = no.level; /尽力依照单位重量价值次序装剩余的物品 while(templevel weighttemplevel ) leftWeight -= weighttemplevel; maxLeft += valuetemplevel; templevel+; /不能装时,用下一个物品的单位重量价值折算到剩余空间。 if( templevel = 0 & sp = num - 1) Queen queen = getQueen(sp); if (null = queen) boolean fl
14、ag = true; while (flag) -sp; if (sp 0) break; if (stacksp.pos.y = num - 1) else stacksp+.pos.y+; flag = false; for (int k = 0; k sp - 1; k+) if (stackk.isUnderControl(stacksp - 1.pos) flag = true; break; else stacksp+ = queen; public Queen getQueen(int x) boolean flag = true; int y = 0; while (flag) flag = false; for (int i = 0; i x; i+) if (stacki.isUnderControl(new Point(x, y) flag = true; break; if (flag & y = num) return null; return new Queen(new Point(x, y); 判定是否冲突public boolean isUnderControl(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025 年单招建筑消防技能测试题(附答案)
- 【低空物流】低空经济智慧物流产教融合实训基地建设与运营管理方案
- 肿瘤学进展及靶向治疗
- 2027年寒假开学摸底考试九年级英语练习卷及答案
- 老年病科护理特色与改进措施
- 急诊科医疗紧急处置的法律责任保险理赔时效
- B7-H3基因调控肿瘤免疫治疗的新进展-20250917-164411
- 2027年安徽省中考三模英语押题密卷及答案解析
- 2027年春季开学考试高三语文练习卷电子版
- 耳鼻喉疾病康复与护理技巧解析讲座
- 2026重庆綦江区国有企业社会招聘管理人员15人笔试参考题库及答案解析
- 2026年中级经济师《建筑与房地产经济》真题及答案
- ASTM D5276-23 中文版(运输包装件自由跌落测试标准 完整原文 + 不同重量跌落高度对照表)
- 室外给水管道及设备安装工艺标准
- 2026年测绘地理信息安全考试题库及答案
- 肿瘤类器官模型应用
- 《跨越边界的社区:北京》阅读记录
- 《JBT 20114.4-2009 糖浆剂瓶封口机》专题研究报告
- 《JBT 10789-2007高压晶体炉 TDR-GY系列液封直拉法高压晶体炉》专题研究报告
- 2026年希望杯IHC五年级数学竞赛试卷(W卷)(含详解)
- (2025年)福建能化集团招聘笔试题附答案
评论
0/150
提交评论