孙锋-4.8分.txt

这是很不错的计算机算法

#include<fstream.h>
#include<stdlib.h> 
#include<stdio.h>
int n;
int totalweight;
int *data;
int *bestx;
void readData()
{
	ifstream inStream;
	inStream.open("input.txt");

	if(!inStream)
	{
		cerr << "Error open file.\n";
		return;
	}

	inStream >> n;
    inStream >> totalweight;
	data = new int[n+1];
	for(int i=1; i<=n; i++)
	{
		inStream >> data[i];
	}
	bestx=new int[n+1];
    for(i=1; i<=n; i++)
	{
		bestx[i]=0;
	}
	inStream.close();
}
void writeData(int i)
{     
    ofstream outStream;
	outStream.open("output.txt");

	//如果打开文件失败，那么输出提示信息；
	if(!outStream)
	{
		cerr << "Error open file.\n";
		return;
	}
	outStream<<i<<endl;
	outStream.close();	
}
//处理装载问题
int Maxloading(int w[],int c,int n,int bestx[])
{
  int i=1;
  int *x=new int[n+1];
  int bestw=0,cw=0,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++;
	  }
  }
}

void main()
{readData();
 writeData(Maxloading(data,totalweight,n,bestx)); 
}