// 裝載問題遞歸算法

#include <iostream.h>
#include <iomanip.h>
const int n=5;  //集裝箱數

template <class Type>
class Loading
{
	friend MaxLoading(Type [], Type, Type, int []);
private:
	void Backtrack(int i);
	int	*x,  //當前解
		*bestx;  // 當前最優解
	Type *w,  // 集裝箱重量
		c1,  // 第一艘船的載重量
		c2,  // 第二艘船的載重量
		cw,  // 當前裝載的重量
		bestw,  // 當前最優裝載重量
		r;  // 剩余集裝箱的重量
};

template <class Type>
void Loading <Type>::Backtrack(int i)
{
	// 搜索第i層結點
	if (i+1>n)
	{
		// 到達葉結點
		if (cw>bestw)
		{
			bestw=cw;
			for (int j=0; j<n; j++) bestx[j]=x[j];
		}
		return;
	}

	// 搜索子樹
	r-=w[i];
	if (cw+w[i]<=c1)
	{
		// 搜索左子樹
		x[i]=1;
		cw+=w[i];
		Backtrack(i+1);
		cw-=w[i];
	}
	if (cw+r>bestw)
	{
		// 搜索右子樹
		x[i]=0;
		Backtrack(i+1);
	}
	r+=w[i];
}

template <class Type>
Type MaxLoading(Type w[], Type c1, Type c2, int bestx[])
{
	Loading <Type> X;
	// 初始化X
	X.x=new int [n];
	X.w=w;
	X.c1=c1;
	X.c2=c2;
	X.bestx=bestx;
	X.bestw=0;
	X.cw=0;
	X.r=0;
	for (int i=0; i<n; i++) X.r+=w[i];

	X.Backtrack(0);  // 從根結點開始搜索
	delete [] X.x;
	return X.bestw;  // 返回最優裝載重量
}

void main()
{
	int w[]={10,40,20,50,30}, c1=80, c2=70, x[n]={0};
	cout<<"\n c1 = "<<c1<<"\n\n c2 = "<<c2<<"\n\n W :";
	for (int i=0; i<n; i++) cout<<setw(4)<<w[i];

	cout<<"\n\n BestW = "<<MaxLoading(w,c1,c2,x);
	cout<<"\n\n X1:";
	for (i=0,c1=0; i<n; i++)
	{
		cout<<setw(4)<<x[i];
		if (!x[i]) c1+=w[i];
	}
	if (c1>c2) cout<<"\n\n No Solusion (c2="<<c1<<")";
	else
	{
		cout<<"\n\n X2:";
		for (i=0; i<n; i++) cout<<setw(4)<<(x[i]?0:1);
	}
	cout<<"\n\n";
}