装载问题递归算法.cpp

回溯法实现多个经典算法

// 装载问题递归算法

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