loading.cpp

用回溯法求解装载问题

#include<iostream>
#include<fstream>
using namespace std;
template<class Type>
class Loading{
	friend Type MaxLoading(Type [],Type,int,int []);
	private:
		void Backtrack(int i);
		int n,
			*x,
			*bestx;
		Type *w,
			 c,
			 cw,
			 bestw,
			 r;
};

template <class Type>
void Loading<Type>::Backtrack(int i)
{
	if(i>n){
		if(cw>bestw){
			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];
}

template<class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[])
{
	Loading<Type> 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;
	X.r=0;
	for(int i=1;i<=n;i++)
		X.r+=w[i];
	X.Backtrack(1);
	delete [] X.x;
	return X.bestw;
}
void main()
{
	ifstream fin("input.txt");
	ofstream fout("ouput.txt");
	int *w;
	int *bestx;
	int n;
    int c;
	fin>>n;
	fin>>c;
	w=new int[n+1];
	bestx=new int[n+1];
	for(int k=1;k<=n;k++)
		fin>>w[k];
    for(int r=1;r<=n;r++)
		bestx[r]=0;
	fout<<"最优装载重量"<<MaxLoading<int>(w,c,n,bestx)<<endl<<"装载的方式："<<endl;
	for(int s=1;s<=n;s++)
		fout<<bestx[s]<<'\t';
	fin.close();
	fout.close();
	
}