/*
當(dāng)i<=n時，當(dāng)前擴(kuò)展結(jié)點z是子集樹中的一個內(nèi)部結(jié)點。該結(jié)點有x[i]=1和x[i]=0
的兩個兒子結(jié)點。其左兒子結(jié)點表示x[i]=1的情形，僅當(dāng)cw+w[i]<=c的時候才進(jìn)入左子樹，遞歸地對
左子樹進(jìn)行搜索。其右兒子結(jié)點表示x[i]=0的情形。由于可行結(jié)點的右兒子結(jié)點總是
可行的，故進(jìn)入右子樹時不需檢查可行性
函數(shù)Backtrack動態(tài)地生成問題的解空間樹。在每個結(jié)點處算法花費o(1)時間。
子集樹中結(jié)點個數(shù)為o(2^n)，故Backtrack所需計算時間為o(2^n)
另外Backtrack還需要額外的o(n)的遞歸?？臻g
*/
/*
構(gòu)造最優(yōu)解，必須在算法中記錄與當(dāng)前最優(yōu)值相應(yīng)的當(dāng)前最優(yōu)解
。為此在類Loading中增加兩個私有數(shù)據(jù)成員x和bestx。x用于記錄從根至
當(dāng)前結(jié)點的路徑；bestx記錄當(dāng)前最優(yōu)解。算法搜索到一個葉結(jié)點處，就修正bestx的值。
*/
#include<iostream>
using namespace std;
template<class Type>
class Loading
{
	friend Type MaxLoading( Type[],Type,int );
	private:
		void Backtrack(int i);
		int n;
		//集裝箱數(shù)量
		Type* w;
		//集裝箱重量數(shù)組
		Type c;
		//第一艘輪船的載重量
		Type cw;
		//當(dāng)前載重量
		Type bestw;
		//當(dāng)前最優(yōu)載重量
};

template<class Type>
void Loading<Type>::Backtrack(int i)
{
	//搜索第i層結(jié)點
	if ( i > n )
	{
		//到達(dá)葉結(jié)點
		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)
{
	// 返回最優(yōu)載重量
	Loading<Type> X;
	X.w = w;
	X.c = c;
	X.n = n;
	X.bestw = 0;
	X.cw = 0;
	//計算最優(yōu)載重量
	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;
}

int main()
{
	int a[3] = 
	{
		10,30,35
	};
	int c = 50;
	MaxLoading(a,50,3);
	Loading<int> b;
	return 0;
}