装载问题.cpp

经典算法之:连续邮资问题,全排列问题,有限期任务安排,整数划分问题,装载问题

#include<iostream.h>

class Loading 
{
	friend int MaxLoading(int w[], int c, int n, int bestx[]);
private:
	void Backtrack(int i);
	int n,	//集装箱数
		*x,	//当前解
		*bestx;	//当前最优解
	int *w,	//集装箱重量数量
		c,	//第一艘轮船的载重量
		cw,	//当前载重量
		bestw,	//当前最优载重量
		r;	//剩余集装箱重量
};


void Loading::Backtrack(int i)
{//搜索第i层结点
	if(i>n)
	{//到达叶结点
		for(int j=1;j<=n;j++)
			bestx[j]=x[j];
		bestw=cw;
		return;
	}
	//搜索字树
	r-=w[i];
	if(cw+w[i]<=c)
	{
		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];
}

int MaxLoading(int w[], int c, int n, int bestx[])
{//返回最优载重量
	Loading X;
	X.x=new int [n+1];
	X.w=w;
	X.c=c;
	X.n=n;
	X.bestx=bestx;
	X.bestw=0;
	X.cw=0;
	//初始化r
	X.r=0;
	for(int i=1;i<=n;i++)
		X.r+=w[i];
	X.Backtrack(1);
	delete [] X.x;
	return X.bestw;
}

int main()
{
	int n,c;
	cout<<"请输入集装箱个数:";
	cin>>n;
	int *w=new int [n+1];
	cout<<"请输入各个集装箱的重量:";
	for(int i=1;i<=n;i++)
		cin>>w[i];
	cout<<"请输入第一艘轮船的载重量:";
	cin>>c;
	int *bestx=new int [n+1];
	int b;
	b=MaxLoading(w,c,n,bestx);
	cout<<b<<endl;
	for(i=1;i<=n;i++)
		cout<<bestx[i]<<" ";
	cout<<endl;
	return 0;
}