林瀚斌-2分.txt

这是很不错的计算机算法

#include<fstream.h>
#include<stdlib.h>
#include<iomanip.h>
#include<conio.h>

class knap;

//类object定义
class Object
{
  friend knap;
  public:
    int operator < (Object temp) const
    {
      return (d<temp.d);
    }
    Object& operator = (Object& temp)
    {
      id=temp.id;
      d=temp.d;
      return *this;
    }
  private:
    int id;
    float d;
};
 

void swap(Object& a,Object& b)
{
  Object temp=a;
  a=b;
  b=temp;
}

void sort(Object* q,int n)
{
  int i,j;
  Object temp;
  for(i=0;i<n-1;i++)
    for(j=i+1;j<n;j++)
      if(q[i]<q[j]) swap(q[i],q[j]);
}

//类bbnode定义
class bbnode
{
  friend knap;
  private:
    bbnode *parent;
    int lchild;
};
    

class maxheapnode
{
  friend knap;
  public:
    int uprofit;
    maxheapnode& operator = (maxheapnode& temp)
    {
      uprofit=temp.uprofit;
      profit=temp.profit;
      weight=temp.weight;
      level=temp.level;
      ptr=temp.ptr;
      return *this;
    }
  private:    
    int profit;
    int weight;
    int level;
    bbnode *ptr;
};

//类maxheap的定义
class maxheap
{
  private:
    maxheapnode *heap;//堆数组 
    int currentsize;//当前堆元素个数 
    int heapsize;//堆大小 
    void filterdown(int start,int endofheap);//向下调整 
    void filterup(int start);//向上调整 
  public:
    maxheap(int n);//构造函数 
    ~maxheap();//析构函数 
    int insert(maxheapnode& x);//插入函数 
    int removemax(maxheapnode& x);//删除最大值函数 
    int isempty();//判断空函数 
    int isfull();//判断满函数 
    void makeempty();//置空函数 
};

/*构造函数的定义*/ 
maxheap::maxheap(int n)
{
  heapsize=n;//设置堆大小 
  currentsize=0;//设置0表示堆中无结点 
  if(!(heap=new maxheapnode[heapsize]))//分配heap数组
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
}

/*析构函数的定义*/ 
maxheap::~maxheap()
{
  delete[] heap;//释放heap数组所占内存 
}

/*判断空函数的定义*/ 
int maxheap::isempty()
{
  return currentsize==0;
}

/*判断满函数的定义*/ 
int maxheap::isfull()
{
  return currentsize==heapsize;
}

/*置空函数的定义*/ 
void maxheap::makeempty()
{
  currentsize=0;//设定0表示堆中无结点 
}

/*向下调整函数的定义*/ 
void maxheap::filterdown(int start,int endofheap)
{
  int i=start,j=2*i+1;//j是i的左子女 
  maxheapnode temp=heap[i];//预先保存i位置的值 
  while(j<=endofheap)
  {
    if(j<endofheap&&heap[j].uprofit<heap[j+1].uprofit) j++;//选出两子女中更大值位置 
    if(temp.uprofit>=heap[j].uprofit) break;//如果比最大值更大则不需调整 
    else 
    {
      heap[i]=heap[j];//将最大值移动到根位置 
      i=j;//设置新的根位置 
      j=2*j+1;//新的左子女位置，继续向下调整 
    }
  }
  heap[i]=temp;//将初始位置的结点移动到新位置 
}

/*向上调整函数的定义*/ 
void maxheap::filterup(int start)
{
  int j=start,i=(j-1)/2;//j是i的双亲 
  maxheapnode temp=heap[j];//预先保存j位置的值 
  while(j>0)
  {
    if(heap[i].uprofit>temp.uprofit) break;//如果双亲更大则不需调整 
    else
    {
      heap[j]=heap[i];//将最大值移动到双亲位置上 
      j=i;//设置新的子女位置 
      i=(i-1)/2;//新的双亲位置，继续向上调整 
    }
  }
  heap[j]=temp;//将初始位置的结点移动到新位置 
}

/*插入函数的定义*/ 
int maxheap::insert(maxheapnode& x)
{
  if(currentsize==heapsize)//堆已满不能插入 
  {
    cout<<"堆已满"<<endl;
    return 0;
  }	
  heap[currentsize]=x;//在堆尾插入元素 
  filterup(currentsize);//向上调整为最大堆 
  currentsize++;//元素个数加1 
  return 1;
}

/*删除最大值函数的定义*/ 
int maxheap::removemax(maxheapnode& x)
{
  if(!currentsize)//堆空不能删除 
  { 
    cout<<"堆已空"<<endl;
    return 0; 
  }
  x=heap[0];//堆首元素赋给x 
  heap[0]=heap[currentsize-1];//堆尾元素移动到堆首	    
  currentsize--;//元素个数减1 
  filterdown(0,currentsize-1);//向下调整为最大堆 
  return 1;
}
/*------------类minheap的定义结束-----------------*/


class knap
{
  //friend int knapsack(int*,int*,int,int,int*);
  public:
    knap();
    ~knap();
    void maxknapsack();
    void knapsack();
    void outputtofile();
  private:
    maxheap *h;
    int bound(int i);
    void addlivenode(int up,int cp,int cw,int ch,int level);
    bbnode *e;
    int c;
    int n;
    int *w;
    int *p;
    int cw;
    int cp;
    int *bestx;
};


knap::knap()
{
  int i;//循环控制变量 
  ifstream fin("input.txt",ios::nocreate);//打开输入文件
  fin>>n>>c;
  if(!(w=new int[n+1]))//分配bestx数组
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  if(!(p=new int[n+1]))//分配bestx数组
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  if(!(bestx=new int[n+1]))//分配bestx数组
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  for(i=1;i<=n;i++) fin>>p[i];
  for(i=1;i<=n;i++) fin>>w[i];
  for(i=1;i<=n;i++) bestx[i]=1;
  h=new maxheap(1000);
  cp=cw=0;
  e=NULL;
  fin.close();
}

knap::~knap()
{
  delete[] p;
  delete[] w;
  delete[] bestx;
  delete h;
}

int knap::bound(int i)
{
  int cleft=c-cw;
  int b=cp;
  while(i<=n&&w[i]<=cleft)
  {
    cleft-=w[i];
    b+=p[i];
    i++;
  }
  if(i<=n) b+=p[i]*cleft/w[i];
  return b;
}

void knap::addlivenode(int up,int cp,int cw,int ch,int level)
{
  bbnode *b=new bbnode;
  b->parent=e;
  b->lchild=ch;
  maxheapnode N;
  N.uprofit=up;
  N.profit=cp;
  N.weight=cw;
  N.level=level;
  N.ptr=b;
  h->insert(N);
}

void knap::maxknapsack()
{
  int i=1,j;
  int bestp=0;
  int up=bound(1);
  while(i!=n+1)
  {
    int wt=cw+w[i]; 
    if(wt<=c)
    {
      if(cp+p[i]>bestp) bestp=cp+p[i];
      addlivenode(up,cp+p[i],cw+w[i],1,i+1);
    }
    up=bound(i+1);
    if(up>=bestp) addlivenode(up,cp,cw,0,i+1);
    maxheapnode N;
    h->removemax(N);
    e=N.ptr;
    cw=N.weight;
    cp=N.profit;
    up=N.uprofit;
    i=N.level;
  }
  for(j=n;j>0;j--)
  {
    bestx[j]=e->lchild;
    e=e->parent;
  }
  //return cp;
}

void knap::knapsack()
{
  int i;
  int W=0,P=0;
  Object *q=new Object[n];
  for(i=1;i<=n;i++)
  {
    q[i-1].id=i;
    q[i-1].d=1.0*p[i]/w[i];
    P+=p[i];
    W+=w[i];
  }
  if(W<=c) {cp=P;return;}
  sort(q,n);
  int *pp=new int[n+1];
  int *ww=new int[n+1];
  for(i=1;i<=n;i++)
  {
    pp[i]=p[i];
    ww[i]=w[i];
  }
  for(i=1;i<=n;i++)
  {
    p[i]=pp[q[i-1].id];
    w[i]=ww[q[i-1].id];
  }
  maxknapsack();
  int *bestxx=new int[n+1];
  for(i=1;i<=n;i++) bestxx[i]=bestx[i];
  for(i=1;i<=n;i++) bestx[q[i-1].id]=bestxx[i];
  delete[] pp;
  delete[] ww;
  delete[] bestxx;
}


void knap::outputtofile()
{
  ofstream out("output.txt");//创建输出文件
  out<<cp<<endl; //输出
  for(int i=1;i<=n;i++)
  {
    out<<bestx[i]<<" ";//输出最优解信息 
  }
  out.close();//关闭输出文件
}

void main()
{
  knap go;
  go.knapsack();
  go.outputtofile();
}