回溯法解装载问题.cpp

算法分析中

/*
当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;
}

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