余新华.txt

这是很不错的计算机算法

/*最优装载问题求解程序*/
/*本程序运行前提：
  在源程序目录下存在input.txt文件，并且该文件已经按一定格式存储若干值
/*本程序在tc++3.0和vc++6.0上运行通过*/
#include<fstream.h>
#include<stdlib.h>
#include<iomanip.h>


/*普通函数声明部分*/ 
void inputfromfile(int&,int&,int*&);
void mergesort(int*,int,int*,int*);
void mergepass(int*,int*,int,int,int*,int*);
void merge(int*,int*,int,int,int,int*,int*);
int loading(int*&,int*,int,int);
void outputtofile(int*,int,int);

/*主程序部分*/ 
int main()
{
  int n,c,*w,*x;
  inputfromfile(n,c,w);//从文件获取所需值
  int remain=loading(x,w,c,n);//装载并返回剩下的装载体积  
  outputtofile(x,c-remain,n);//输出已用装载量和装载信息到文件 
  delete[] w;//释放数组w所占内存 
  delete[] x;//释放数组x所占内存 
  return 0;
}

/*inputfromfile函数定义*/ 
void inputfromfile(int& n,int& c,int*& w)
{
  ifstream fin("input.txt",ios::nocreate);//打开输入文件
  if(!fin) //如果文件不存在 
  {
    cerr<<"文件不存在";
    exit(-1);
  } 
  fin>>n>>c;//读出集装箱个数和轮船载重量 
  if(!(w=new int[n]))
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  } 
  for(int i=0;i<n;i++)//读出每个集装箱的重量 
    fin>>w[i];
  fin.close();//关闭输入文件 
}

void mergesort(int*a,int n,int* t,int* temp)//合并排序 
{
  int i;//循环控制变量 
  int *b;//合并交换用的数组 
  if(!(b=new int[n]))
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  int s=1;//将合并的子数组长度 
  while(s<n)//长度小于n循环合并 
  {
    mergepass(a,b,s,n,t,temp);//合并到数组b 
    for(i=0;i<n;i++) temp[i]=t[i];//用新的位置信息赋值temp数组 
    s+=s;//长度加倍 
    mergepass(b,a,s,n,t,temp);//合并到数组a
    for(i=0;i<n;i++) temp[i]=t[i];//用新的位置信息赋值temp数组
    s+=s;//长度加倍
  }
  delete[] a;//释放数组a所占内存
  delete[] b;//释放数组b所占内存
}


/*mergepass函数定义*/
void mergepass(int*x,int*y,int s,int n,int* t,int* temp)//合并大小为s的相邻子数组 
{
  int i=0;//循环控制变量 
  while(i<=n-2*s)//合并大小为s的相邻2段子数组
  {
    merge(x,y,i,i+s-1,i+2*s-1,t,temp);//合并 
    i=i+2*s;//后两个相邻子数组 
  }
  if(i+s<n) merge(x,y,i,i+s-1,n-1,t,temp);//剩下s--2s个元素合并 
  else//剩下不足s个元素直接赋值 
    for(int j=i;j<=n-1;j++) {y[j]=x[j];t[j]=temp[j];}//将该位置在初始数组w中的位置赋给t 
}


/*merge函数定义*/ 
void merge(int*c,int*d,int l,int m,int r,int* t,int* temp)//合并c[l:m]和c[m+1:r]到d[l:r] 
{
  int i=l,j=m+1,k=l;
  int q;//循环控制变量 
  int pos;
  while(i<=m&&j<=r)
  {
    if(c[i]<=c[j]) 
    {
      d[k++]=c[i++];//c[i]更小，先存入d
      pos=i-1;//记下位置 
    } 
    else           
    {
      d[k++]=c[j++];//c[j]更小，先存入d
      pos=j-1;//记下位置
    } 
    t[k-1]=temp[pos];//将该位置在初始数组w中的位置赋给t 
  }
  if(i>m)//c[m+1:r]还有剩余元素 
    for(q=j;q<=r;q++) {d[k++]=c[q];t[k-1]=temp[q];}//将该位置在初始数组w中的位置赋给t
  else//c[l:m]还有剩余元素
    for(q=i;q<=m;q++) {d[k++]=c[q];t[k-1]=temp[q];}//将该位置在初始数组w中的位置赋给t
}

/*loading函数定义*/ 
int loading(int*&x,int*w,int c,int n)
{
  int i;//循环控制变量 
  int *a,*t,*temp;//a保存w数组信息；t和temp保存排序后每个元素在w数组中的位置信息
                  //其中t保存每次合并后的位置信息，temp保存合并前的临时位置信息 
  if(!(x=new int[n]))
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  if(!(a=new int[n]))
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  if(!(t=new int[n]))
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  } 
  if(!(temp=new int[n]))
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  } 
  for(i=0;i<n;i++) t[i]=temp[i]=i;//t和temp赋初值 
  for(i=0;i<n;i++) a[i]=w[i];//a数组赋初值 
  mergesort(a,n,t,temp);
  for(i=0;i<n;i++) x[i]=0;//x数组赋初值 
  for(i=0;i<n&&w[t[i]]<=c;i++)
  {
    x[t[i]]=1;
    c-=w[t[i]];
  }
  delete[] t;//释放数组t所占内存
  delete[] temp;//释放数组temp所占内存
  return c;
}
/*outputtofile函数定义*/ 
void outputtofile(int* x,int c,int n)
{
  ofstream out("output.txt");//创建输出文件
  out<<c<<endl;//输出已用装载量 
  for(int i=0;i<n;i++)
  {
    out<<x[i]<<" ";//输出装载信息 
  }
  out.close();//关闭输出文件 
}