陈顺凡-4.8分.txt

这是很不错的计算机算法

#include <iostream>
#include <fstream>
using namespace std;
//定义载量类
template <class Type>
class Loading
{
 friend Type MaxLoading(Type[],Type,int);
 public:
	 void Backtrack(int i);
	 int n;//集装箱数
	 Type *w,c,cw,bestw,r;//w集装箱重量数组,c轮船的载重量,cw当前载重量,bestw当前最优载重量,r剩余集装重量
};
template <class Type>
void Loading <Type>::Backtrack(int i)
{//搜索第i层结点
	if(i>n){//到达叶结点
		 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)
{//返回最优载重量
	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);
	return X.bestw;
}
//主程序
void main()
{ 
	int i,n,c;
	int *w;
    ifstream fin("input.txt");
	ofstream out("output.txt");
	if(fin.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	fin>>n;//集装箱数
	fin>>c;//轮船载重量
	w=new int[n+1];
	for(i=1;i<=n;i++)
	  fin>>w[i];
   Loading <int> X;
   int bestw=Maxloading(w,c,n);
   out<<bestw;
}