回溯法解装载问题最优解.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;
}
*/

/*
对右子树进行剪枝的改进算法
*/
/*
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;
}
/*
本题采用子集树的结构搜索解空间，从第一层开始搜索
*/