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

template
Queue& Queue::AddLeft(const T& x)
{
if(IsFull())cout<<"queue:no memory"< else
{
front=(front+MaxSize-1)% MaxSize;
queue[(front+1)% MaxSize]=x;
}
return *this;
}

template
Queue& Queue ::Delete(T & x)
{
if(IsEmpty())cout<<"queue:no element(delete)"< else
{
front=(front+1) % MaxSize;
x=queue[front];
}
return *this;
}

template
void Queue ::Output(ostream& out)const
{
for(int i=rear%MaxSize;i>=(front+1)%MaxSize;i--)
out< }

template
ostream& operator << (ostream& out,const Queue& x)
{x.Output(out);return out;}
2、6d3-1.cpp

[cpp]
//装载问题 队列式分支限界法求解
#include "stdafx.h"
#include "Queue.h"
#include
using namespace std;

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;
}

//装载问题 队列式分支限界法求解
#include "stdafx.h"
#inc