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