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

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

一、 实验目的

1、理解分支限界法的概念，掌握分支限界法的基本要素。

2、 掌握设计分支限界法的一般步骤，针对具体问题，能应用分支限界法求解

二、 实验内容

1、问题描述：有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且w1+…+wn<= C1+ C2; 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。

2、数据输入：文件输入或键盘输入。

3、要求：1）完成上述问题的队列式分支限界法解决问题，时间为1 次课。2）完成实验及实验报告。

三、 实验步骤

1、理解方法思想和问题要求。

第 1 页 共 3 页

2、 采用编程语言实现题目要求。

3、 上机输入和调试自己所写的程序。

4、附程序主要代码：#include using namespace std;class MaxHeapQNode{public: MaxHeapQNode *parent; int lchild; int weight; int lev;};struct cmp{ bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b)

const { return a->weight < b->weight; }};int n;int c;int bestw;int w[100];int bestx[100];void InPut(){ scanf(\"%d %d\

scanf(\"%d\&w[i]);}void AddAliveNode(priority_queue, 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(){ priority_queue, cmp > q; // 大顶堆 //定义剩余重量数组r int r[n +1]; r[n] = 0; for(int j = n-j)

r[j] = r[j +1] + w[j +1]; int i =1; MaxHeapQNode *E; int Ew = 0; while(i != n +1)

{ if(Ew + w[i] <= c)

{ AddAliveNode(q, E, Ew + w[i] + r[i], i,1); } AddAliveNode(q, E, Ew + r[i], i, 0);

第 2 页 共 3 页

//取下一节点 E = q、top(); q、pop(); i = E->lev; Ew = E->weight1]; } bestw = Ew; for(int j = n; j > 0;j)

{ bestx[j] = E->lchild; E = E->parent; }}void OutPut(){ printf(\"最优装载量为 %d\\n\装载的物品为 \\n\"); for(int i =1; i <= n; ++i)

if(bestx[i] ==1)

printf(\"%d \

5、实验结果：

4、 装载问题实验分析：

1、将wt<=c和Ew+r>=bestw作为限界判定。

2、为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。

3、装载两只船，先尽可能的装满一艘，再装第二艘。

第 3 页 共 3 页