/*
當i<=n時，當前擴展結點z是子集樹中的一個內部結點。該結點有x[i]=1和x[i]=0
的兩個兒子結點。其左兒子結點表示x[i]=1的情形，僅當cw+w[i]<=c的時候才進入左子樹，遞歸地對
左子樹進行搜索。其右兒子結點表示x[i]=0的情形。由于可行結點的右兒子結點總是
可行的，故進入右子樹時不需檢查可行性
函數Backtrack動態地生成問題的解空間樹。在每個結點處算法花費o(1)時間。
子集樹中結點個數為o(2^n)，故Backtrack所需計算時間為o(2^n)
另外Backtrack還需要額外的o(n)的遞歸棧空間
*/
/*
構造最優解，必須在算法中記錄與當前最優值相應的當前最優解
。為此在類Loading中增加兩個私有數據成員x和bestx。x用于記錄從根至
當前結點的路徑；bestx記錄當前最優解。算法搜索到一個葉結點處，就修正bestx的值。
*/
#include<iostream>
using namespace std;

/*template<class Type>
class Loading
{
	friend Type MaxLoading( Type[],Type,int );
	private:
		void Backtrack(int i);
		int n;
		//集裝箱數量
		Type* w;
		//集裝箱重量數組
		Type c;
		//第一艘輪船的載重量
		Type cw;
		//當前載重量
		Type bestw;
		//當前最優載重量
};

template<class Type>
void Loading<Type>::Backtrack(int i)
{
	//搜索第i層結點
	if ( i > n )
	{
		//到達葉結點
		if ( cw > bestw )
		{
			bestw = cw;
		}

		return;
	}

	//search child tree
	if ( cw + w[i] <= c )
	{
		//x[i]=1;
		cw += w[i];
		Backtrack(i+1);
		cw -= w[i];
		//返回上一層就要減去多加的下層重量
		cout<<cw<<endl;
	}

	Backtrack(i+1);
	//x[i]=0;
}

template <class Type>
Type MaxLoading(Type w[],Type c,int n)
{
	// 返回最優載重量
	Loading<Type> X;
	X.w = w;
	X.c = c;
	X.n = n;
	X.bestw = 0;
	X.cw = 0;
	//計算最優載重量
	cout<<"X.w is: "<<X.w<<endl;
	cout<<"X.c is: "<<X.c<<endl;
	cout<<"X.n is: "<<X.n<<endl;
	cout<<"X.bestw is: "<<X.bestw<<endl;
	cout<<"X.cw is: "<<X.cw<<endl;

	for( int i = 0; i < n; ++i )
	{
		cout<<X.w[i]<<endl;
	}

	X.Backtrack(1);
	cout<<"the bestw is: "<<X.bestw<<endl;
 	return X.bestw;
}
*/

/*
對右子樹進行剪枝的改進算法
*/
/*
template<class Type>
class Loading
{
	friend Type MaxLoading( Type[],Type,int );
	private:
		void Backtrack(int i);
		int n;
		//集裝箱數量
		Type* w;
		//集裝箱重量數組
		Type c;
		//第一艘輪船的載重量
		Type cw;
		//當前載重量
		Type bestw;
		//當前最優載重量
		Type r;
		//剩余的集裝箱重量
};
template<class Type>
void Loading<Type>::Backtrack(int i)
{
	//搜索第i層結點
	if ( i > n )
	{
		//到達葉結點
		if ( cw > bestw )
		{
			bestw = cw;
		}

		return;
	}

	r -= w[i];
	//search child tree
	if ( cw + w[i] <= c )
	{
		//x[i]=1;
		cw += w[i];
		Backtrack(i+1);
		cw -= w[i];
		//返回上一層就要減去多加的下層重量
		cout<<cw<<endl;
	}
	
	if ( cw + r > bestw )
	{
		Backtrack(i+1);
		//x[i]=0;
	}
	r += w[i];
	//返回到當前層的時候剩余重量還是要恢復，也就是恢復到還沒將當前層選為活結點時候的狀態
}

template <class Type>
Type MaxLoading(Type w[],Type c,int n)
{
	//返回最優載重量
	Loading<Type> X;
	X.w = w;
	X.c = c;
	X.n = n;
	X.bestw = 0;
	X.cw = 0;
	//計算最優載重量
	X.r = 0;
	for( int i = 1; i <= n; ++i )
	{
		X.r += w[i];
	}

	X.Backtrack(1);
	cout<<"the bestw is: "<<X.bestw<<endl;
 	return X.bestw;
}*/

/*
最優算法
*/
template<class Type>
class Loading
{
	friend Type MaxLoading( Type[],Type,int,Type[] );
	private:
		void Backtrack(int i);
		int n;
		//集裝箱數量
		int *x;
		//當前解，也就是說記錄了一個路徑
		int *bestx;
		//當前最優解，也就是說記錄了一個路徑
		Type* w;
		//集裝箱重量數組
		Type c;
		//第一艘輪船的載重量
		Type cw;
		//當前載重量
		Type bestw;
		//當前最優載重量
		Type r;
		//剩余的集裝箱重量
};
template<class Type>
void Loading<Type>::Backtrack(int i)
{
	//搜索第i層結點
	if ( i > n )
	{
		//到達葉結點
		if ( cw > bestw )
		{
			for( int j = 1; j <= n; ++j )
			{
				bestx[j] = x[j];
			}
			bestw = cw;
		}

		return;
	}

	r -= w[i];
	//search child tree
	if ( cw + w[i] <= c )
	{
		//x[i]=1;
		cw += w[i];
		Backtrack(i+1);
		cw -= w[i];
		//返回上一層就要減去多加的下層重量
		cout<<cw<<endl;
	}
	
	if ( cw + r > bestw )
	{
		Backtrack(i+1);
		//x[i]=0;
	}
	r += w[i];
	//返回到當前層的時候剩余重量還是要恢復，也就是恢復到還沒將當前層選為活結點時候的狀態
}

template <class Type>
Type MaxLoading( Type w[],Type c,int n,int bestx[] )
{
	//返回最優載重量
	Loading<Type> X;
	X.w = w;
	X.c = c;
	X.n = n;
	X.bestw = 0;
	X.cw = 0;
	//計算最優載重量
	X.x = new int[n+1];
	X.bestx = bestx;
	X.r = 0;
	for( int i = 1; i <= n; ++i )
	{
		X.r += w[i];
	}

	X.Backtrack(1);
	delete X.x;
	cout<<"X.bestw = "<<X.bestw<<endl;
 	return X.bestw;
}

template< class Type >
Type MaxLoading( Type w[], Type c, int n, int bestx[] )
{
	//迭代回溯
	int i = 1;
	//當前層
	int *x = new int[n+1];
	Type bestw = 0;
	//當前最優載重量
	Type cw = 0;
	//當前載重量
	Type r = 0;
	//剩余集裝箱重量
	for( int j = 1; j <= n; ++j )
	{
		r += w[j];
	}
	//搜索子樹
	while(true)
	{
		while( i <= n && cw + w[i] <= c )
		{
			//進入左子樹
			r -= w[i];
			cw += w[i];
			x[i] = 1;
			++i;
		}
		if ( i > n )
		{
			for( int j = 1; j <= n; ++j )
			{
				bestx[j] = x[j];
			}
			bestw = cw;
		}
		else
		{
			//進入右子樹
			r -= w[i];
			x[i] = 0;
			++i;
		}

		while( cw + r <= bestw )
		{
			//剪枝回溯
			i--;
			while(i > 0 && !x[i] )
			{
				//從右子樹回溯
				r += w[i];
				--i;
			}
			if ( i == 0 )
			{
				delete []x;
				return bestw;
			}
			//進入右子樹
			x[i] = 0;
			cw -= w[i];
			++i;
		}
	}

}
int main()
{
	int a[4] = 
	{
		0,10,30,33
	};
	int c = 50;
	int b[4] = {0,0,0,0};
	MaxLoading(a,50,3,b);
	return 0;
}
/*
本題采用子集樹的結構搜索解空間，從第一層開始搜索
*/