用分支限界算法解装载问题详解

1、湖州师范学院实验报告课程名称：算法实验五： 分支限界算法一、 实验目的1、理解分支限界法的概念，掌握分支限界法的基本要素。2、 掌握设计分支限界法的一般步骤，针对具体问题，能应用分支限界法求解二、 实验内容1、问题描述：有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且w1+wn= C1+ C2; 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 2、数据输入：文件输入或键盘输入。3、要求：1）完成上述问题的队列式分支限界法解决问题，时间为 1 次课。2）独立完成实验及实验报告。三、 实验步骤1、 理解方法思想和

2、问题要求。2、 采用编程语言实现题目要求。3、 上机输入和调试自己所写的程序。4、附程序主要代码：#include using namespace std;class MaxHeapQNodepublic: MaxHeapQNode *parent; int lchild; int weight; int lev;struct cmp bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const return a-weight weight; ;int n;int c;int bestw;int w100;int bestx100;void

3、 InPut() scanf(%d %d, &n, &c); for(int i = 1; i = n; +i) scanf(%d, &wi);void AddAliveNode(priority_queueMaxHeapQNode *, vector, cmp &q, MaxHeapQNode *E, int wt, int i, int ch) MaxHeapQNode *p = new MaxHeapQNode; p-parent = E; p-lchild = ch; p-weight = wt; p-lev = i + 1; q.push(p);void MaxLoading() p

4、riority_queueMaxHeapQNode *, vector, cmp q; / 大顶堆 /定义剩余重量数组r int rn + 1; rn = 0; for(int j = n - 1; j 0; -j) rj = rj + 1 + wj + 1; int i = 1; MaxHeapQNode *E; int Ew = 0; while(i != n + 1) if(Ew + wi lev; Ew = E-weight - ri - 1; bestw = Ew; for(int j = n; j 0; -j) bestxj = E-lchild; E = E-parent; void OutPut() printf(最优装载量为 %dn, bestw); printf(装载的物品为 n); for(int i = 1; i = n; +i) if(bestxi = 1) printf(%d , i);int main() InPut(); MaxLoading(); OutPut();5、实验结果：4、 装载问题实验分析：1、将wt=best