最大堆分支限界法解最优装载问题.cpp

算法分析中

#include<iostream>
#include <algorithm>
#include <deque>
using namespace std;

/*
优先队列式分支限界法
解装载问题的优先队列分支限界法将活结点表存储于一个最大优先队列中，活结点x
在优先队列中的定义为从根结点到结点x所相应的载重量再加上剩余集装箱的重量之和

优先队列中优先级最大的活结点成为下一个扩展结点
优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应
的载重量与其优先级相同。
因此在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点
则可以断言该叶结点所相应的解为最优解

有两种方式记录最优路径
（1） 在每一个活结点中保存从解空间树的根结点到该结点的路径，在算法确定了
达到最优值的叶结点时，就在该叶结点处同时得到相应的最优解.
（2） 在算法的搜索过程中保存当前已经构造出的部分解空间树
，到达最有值的叶结点时，就可以在解空间树从该结点开始向根结点回溯
构造出相应的最优解，程序采用第二种策略。

*/
/*
堆结构：
堆就是一棵完全二叉树
数组来存储各个结点
数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在2*i+1上，当然了存储下标从1开始

堆序性质
在一个堆中，对于每一个结点x，x的父亲中的关键字小于x中的关键字，根结点除外
*/

/*
掌握如何实现优先队列，利用二叉堆，孩子结点都大于父亲结点
*/

template<class Type>
class MaxHeap
{
	public:
		Type *H;
		int Capacity;
		int Size;
	public:
		MaxHeap(int n)
		{
			H = NULL;
			//H = (Type*)malloc( sizeof( Type ) * ( n + 1 ) );
			H = new Type[n+1];
			Capacity = n;
			Size = 0;
		};
		MaxHeap( MaxHeap& a )
		{
			//要排除自赋值的情况
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[size];
				}
			}
		};

		/*
		基本的堆插入操作
		为了将node插入到堆中
		首先在下一个空闲位置++Size处，创建一个空穴，否则该堆将不是完全树
		如果x可以放在该穴中而不破坏堆的序，那么插入完成
		否则我们把空穴的父亲结点上的元素移动到该穴中，这样空穴就朝着根的方向上行一步
		继续该过程直到x能被放入空穴为止
		*/
		void Insert( Type& node )
		{
			//插入元素的时候按照从大到顺序
			for( int i = ++Size; H[ i / 2 ] < node && i != 0; i /= 2 )
			{
				H[i] = H[ i / 2 ];
			}
			//一定要注意从下标一开始的时候，添加如何进行比较才行
			H[i] = node;
			H[1].print();
			
			for( int k = 1; k <= Size; ++k )
			{
				H[k].print();
			}
			
		};

		/*
		当删除一个最小元时
		在根结点处产生一个空穴。
		由于现在堆少了一个元素，因此堆中最后一个元素必须移动到该堆的某个地方
		如果x可以放到空穴中，那么DeleteMin完成
		否则应该将两个儿子中较小者移入空穴
		这样空穴就向下推了一层。重复该步骤直到x可以被放入空穴中
		*/
		void DeleteMin( Type& node )
		{
			int i,Child;
			Type MinElement,LastElement;
			node = H[1];
			LastElement = H[Size--];

			for( i = 1; i * 2 <= Size; i = Child )
			{
				Child = i * 2;
				if ( ( Child != Size && H[ Child + 1 ] > H[ Child ] ) )
				{
					Child++;
				}

				if ( LastElement < H[ Child ] )
				//找到孩子结点中最大的一个覆盖孩子结点
				{
					H[ i ] = H[ Child ];      
				}
				else
				{
					break;
				}
			}
			//same to H[ Child ] = LastElement
			H[ i ] = LastElement;
		};
};

template< class Type > class HeapNode;
class bbnode
{
	friend void AddLiveNode( MaxHeap< HeapNode<int> >& H,
							 bbnode * E,
							 int wt,
							 bool ch,
							 int lev
							);
	friend int MaxLoading( int *w,int c,int n,int *best );
public:
	bbnode()
	{
		//cout<<"bbnode constructor"<<endl;
		parent = 0;
		LChild = 0;
	};

	bbnode( bbnode& a )
	{
		parent = a.parent;
		LChild = a.LChild;
	};

	bbnode& operator=(bbnode& a)
	{
		cout<<"copy bbnode"<<endl;
		parent = a.parent;
		LChild = a.LChild;
		return *this;
	};

public:
	bbnode *parent;
	//指向父结点的指针
	bool LChild;
	//左儿子结点标志
};

template< class Type >
class HeapNode
{
	friend void AddLiveNode( MaxHeap< HeapNode< Type > > &H,
							 bbnode* E,
							 Type wt,
							 bool ch,
							 int lev );
	friend Type MaxLoading( Type* w,Type c,int n,int*  best );
public:
	operator Type() const
	{
		return uweight;
	};
	HeapNode()
	{
		ptr = new bbnode();
		uweight = 1000;
		level = 0;
	};

	HeapNode( HeapNode& a )
	{
		if ( ptr != a.ptr && ptr != NULL )
		{
			ptr->parent = a.ptr->parent;
			ptr->LChild = a.ptr->LChild;
		}
		uweight = a.uweight;
		level = a.level;
	};
	HeapNode& operator=(const HeapNode& a)
	{
		if ( ptr != a.ptr && ptr != NULL )
		{
			ptr->parent = a.ptr->parent;
			ptr->LChild = a.ptr->LChild;
		}
		uweight = a.uweight;
		level = a.level;
		return *this;
	};

	bool operator <( HeapNode& a ) const
	{
		return uweight < a.uweight;
	};

	bool operator >( HeapNode& a ) const
	{
		return uweight > a.uweight;
	};
	void print()
	{
		//cout<<"ptr->LChild = "<<ptr->LChild<<endl;
		//cout<<"uweight = "<<uweight<<endl;
	}
private:
	bbnode* ptr;
	//指向活结点在子集树中相应结点的指针
	Type uweight;
	//活结点优先级（上界）
	int level;
	//活结点在子集树中所处的层序号
};

template< class Type >
void AddLiveNode( MaxHeap< HeapNode< Type > >&H,
				  bbnode *E,
				  Type wt,
				  bool ch,
				  int lev )
{
	//将活结点加入到表示活结点的优先队列的最大堆H中
	bbnode *b = new bbnode;
	b->parent = E;
	b->LChild = ch;
	HeapNode< Type > N;
	N.uweight = wt;
	N.level = lev;
	N.ptr = b;
	H.Insert( N );
}

template< class Type >
Type MaxLoading( Type w[],Type c,int n,int *bestx )
{
	MaxHeap< HeapNode< Type > > H(10);
	Type * r = new Type[n+1];
	r[n] = 0;
	for( int j = n - 1; j > 0; --j )
	{
		r[j] = r[j+1] + w[j+1];
	}
	//初始化
	int i = 1;
	//当前扩展结点所处的层
	bbnode *E = 0;
	//当前扩展结点
	Type Ew = 0;
	//扩展结点所相应的载重量
	//搜索子集空间树
	while( i != n + 1 ) 
	{
		cout<<"i = "<<i<<endl;
		if ( Ew + w[i] <= c )
		{
			//cout<<"Ew + w[i] = "<<Ew+w[i]<<endl;
			//cout<<"uweight = "<<Ew + w[i] + r[i]<<endl;
			AddLiveNode( H,E,Ew + w[i] + r[i],true,i + 1 );
		}
		
		AddLiveNode( H,E,Ew + r[i],false,i + 1 );
		
		HeapNode< Type > N;
		H.DeleteMin( N );
		i = N.level;
		E = N.ptr;
		Ew = N.uweight - r[i-1];
	}
	for( j = n; j > 0; --j )
	{
		bestx[j] = E->LChild;
		E = E->parent;
		cout<<"bestx["<<j<<"] = "<<bestx[j]<<endl;
	}
	cout<<Ew<<endl;
	return Ew;
}

int main()
{
	//HeapNode<int> node;
	int a[4] = 
	{
		0,10,30,33
	};
	int c = 50;
	int b[4] = {0,0,0,0};
	MaxLoading<int>(a,50,3,b);
	return 0;
}