0034算法笔记――[分支限界法]最优装载问题 (三)

const int N = 4;

template
class QNode
{
template
friend void EnQueue(Queue*>&Q,Type wt,int i,int n,Type bestw,QNode*E,QNode *&bestE,int bestx[],bool ch);

template
friend Type MaxLoading(Type w[],Type c,int n,int bestx[]);

private:
QNode *parent; //指向父节点的指针
bool LChild; //左儿子标识
Type weight; //节点所相应的载重量
};

template
void EnQueue(Queue*>&Q,Type wt,int i,int n,Type bestw,QNode*E,QNode *&bestE,int bestx[],bool ch);

template
Type MaxLoading(Type w[],Type c,int n,int bestx[]);

int main()
{
float c = 70;
float w[] = {0,20,10,26,15};//下标从1开始
int x[N+1];
float bestw;

cout<<"轮船载重为："< cout<<"待装物品的重量分别为："< for(int i=1; i<=N; i++)
{
cout< }
cout< bestw = MaxLoading(w,c,N,x);

cout<<"分支限界选择结果为:"< for(int i=1; i<=4; i++)
{
cout< }
cout< cout<<"最优装载重量为："<
return 0;
}

//将活节点加入到活节点队列Q中
template
void EnQueue(Queue*>&Q,Type wt,int i,int n,Type bestw,QNode*E,QNode *&bestE,int bestx[],bool ch)
{
if(i == n)//可行叶节点
{
if(wt == bestw)
{
//当前最优装载重量
bestE = E;
bestx[n] = ch;
}
return;
}
//非叶节点
QNode *b;
b = new QNode;
b->weight = wt;
b->parent = E;
b->LChild = ch;
Q.Add(b);
}

template
Type MaxLoading(Type w[],Type c,int n,int bestx[])
{//队列式分支限界法，返回最优装载重量，bestx返回最优解
//初始化
Queue*> Q; //活节点队列
Q.Add(0); //同层节点尾部标识
int i = 1; //当前扩展节点所处的层
Type Ew = 0, //扩展节点所相应的载重量
bestw = 0, //当前最优装载重量
r = 0; //剩余集装箱重量

for(int j=2; j<=n; j++)
{
r += w[j];
}

QNode *E = 0, //当前扩展节点
*bestE; //当前最优扩展节点

//搜索子集空间树
while(true)
{
//检查左儿子节点
Type wt = Ew + w[i];
if(wt <= c)//可行节点
{
if(wt>bestw)
{
bestw = wt;
}
EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);
}

//检查右儿子节点
if(Ew+r>bestw)
{
EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);
}
Q.Delete(E);//取下一扩展节点

if(!E)//同层节点尾部
{
if(Q.IsEmpty())
{
break;
}
Q.Add(0); //同层节点尾部标识
Q.Delete(E); //取下一扩展节点
i++; //进入下一层
r-=w[i]; //剩余集装箱重量
}
Ew =E->weight; //新扩展节点所对应的载重量
}

//构造当前最优解
for(int j=n-1; j>0; j--)
{
bestx[j] = bestE->LChild;
bestE = bestE->parent;
}
return bestw;
} 程序运行结果如图：

2、优先队列式分支限界法求解

解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。
优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。
在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。

算法具体代码实现如下：

1、MaxHeap.h

[cpp]
template
class MaxHeap
{
public:
MaxHeap(int MaxHeapSize = 10);
~MaxHeap() {delete [] heap;}
int Size() const {return CurrentSize;}

T Max()
{ //查
if (CurrentSize == 0)
{
throw OutOfBounds();
}
return heap[1];
}

MaxHeap& Insert(const T& x); //增
MaxHeap& DeleteMax(T& x); //删

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 T[MaxSize+1];
CurrentSize = 0;
}

template
MaxHeap& MaxHeap::Insert(const T& x)
{// Insert x into the max heap.
if (CurrentSize == MaxSize)
{
cout<<"no space!"< return *this;
}

// 寻找新元素x的位置
// i——初始为新叶节点的位置，逐层向上，寻找最终位置
int i = ++Curr