ship.cpp

用动态规划法实现装载问题

#include "iostream.h"
#include "fstream.h"

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

		void Backtrack(int 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;

	//初始化r为全体物品的重量和
	for(int i=1; i<=n; i++) {
		x.r += w[i];
	}

	x.Backtrack(1);
	delete[] x.x;

	return x.bestw;
}

template<class Type>
void Loading<Type>::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 main(int argc, char* argv[]) {
	int n;
	int allWeight;
	ifstream fin("input.txt");
	fin >> n >> allWeight;		//读入集装箱数和货船一所能容下的总重量

	int* w = new int[n];
	int i = 0;
	for(; i<n; i++) {			//读入每一个集装箱的重量
		fin>>w[i];
	}

	fin.close();

	int* bestx = new int[n];	//定义并初始化最优解数组
	for(i = 0; i<n; i++) {
		bestx[i] = 0;
	}

	MaxLoading(w,allWeight,n,bestx);

	for(i = 0; i<n; i++) {		//输出最优解
		cout<<bestx[i]<<"   ";
	}

	cout<<endl;

	return 0;
}