《装载问题5种解决方案》由会员分享，可在线阅读，更多相关《装载问题5种解决方案（35页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计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 代码 .274.3 测试截图 .315
2、贪心算法 .315.1 算法分析 .315.2 代码 .315.3 测试截图 .35算法分析与设计3 / 34一问题定义有一批共有 n 个集装箱要装上两艘载重量分别为 c1 和 c2 的轮船，其中集装箱 i 的重量为 wi, 且重量之和小于(c1 + c2)。装载问题要求确定是否存在一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有，找出一种装载方案。二解决方案1 优先队列式分支限界法求解1.1 算法分析活结点 x 在优先队列中的优先级定义为从根结点到结点 x 的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点 x 为根的子树中所有
3、结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。1.2 代码1.2-1/MaxHeap.htemplate class MaxHeap public: MaxHeap(int MaxHeapSize = 10); MaxHeap() delete heap; int Size() const return CurrentSize; 算法分析与设计4 / 34T Max() /查找 if (CurrentSize = 0) throw OutOf
4、Bounds(); return heap1; MaxHeap /增 MaxHeap /删 void Initialize(T a, int size, int ArraySize); private: int CurrentSize, MaxSize; T *heap; / element array ; template MaxHeap:MaxHeap(int MaxHeapSize) / Max heap constructor. MaxSize = MaxHeapSize; heap = new TMaxSize+1; CurrentSize = 0; template MaxHeap
5、& MaxHeap:Insert(const T& x) / Insert x into the max heap. 算法分析与设计5 / 34if (CurrentSize = MaxSize) cout heapi/2) / i 不是根节点，且其值大于父节点的值，需要继续调整 heapi = heapi/2; / 父节点下降 i /= 2; / 继续向上，搜寻正确位置 heapi = x; return *this; template MaxHeap& MaxHeap:DeleteMax(T& x) / Set x to max element and delete max element
6、 from heap. / check if heap is empty if (CurrentSize = 0) cout= heapci) break; / 是，i 就是 y 的正确位置，退出 / 否，需要继续向下，重整堆 heapi = heapci; / 大于父节点的孩子节点上升 i = ci; / 向下一层，继续搜索正确位置 ci *= 2; heapi = y; return *this; 算法分析与设计7 / 34template void MaxHeap:Initialize(T a, int size,int ArraySize) / Initialize max heap to array a. delete heap; heap = a; CurrentSize = size; MaxSize = ArraySize; / 从最后一个内部节点开始，一直到根，对每个子树进行堆重整 for (int i = CurrentSize/2; i = 1; i-) T y = heapi; / 子树根节点元素 / find place to put y int c = 2*i; / parent of c is target / location for y while (c = heapc) break; / y
