李道强-3分.txt

这是很不错的计算机算法

#include <iostream>
#include <fstream.h>

//这是一个数组形式的大根堆
template <class Type> class MaxHeap
{
public:
  MaxHeap(unsigned MaxSize);
  ~MaxHeap();
  void MakeEmpty();              //清空堆
  bool DeleteMax(Type &Node);    //移除顶点。并将该顶点存入Node
  bool Insert(const Type Node); //插入新元素
  bool GetMax(Type &Node);      //得到最大值，即顶点
public:   //内联函数
  bool IsFull() const  {return CurrentSize==MaxHeapSize;}//判断大根堆是否已满
  bool IsEmpty() const{return CurrentSize==0;}//判断大根堆是否为空
protected://调整大根堆函数
  void FilterUp(unsigned i);      //由底向上调整大根堆,将i结点向上层移动到一个正确位置
  void FilterDown(unsigned i,unsigned m);  //从上而下高速大根堆，将i向下层移动至一个m结点前的正确的位置
private: //内部数据
  Type * Heap;                //元素数组指针
  unsigned MaxHeapSize;        //最大元素个数
  unsigned CurrentSize;        //数组当前有效长度
  enum{DefaultSize= 20};      //数组默认长度
};

//构造函数  MaSize 大根堆数组的长度
template <class Type> MaxHeap<Type>::MaxHeap(unsigned MaxSize)
{
  MaxHeapSize=(DefaultSize>MaxSize)? DefaultSize:MaxSize;  //初始化数组最大值
  Heap=new Type[MaxHeapSize];      //给该类新建一个数组
  CurrentSize=0;            //初始化数组当前长度
}

//析构函数
template <class Type> MaxHeap<Type>::~MaxHeap()
{
  delete [] Heap;            //释放数组空间
}

//由底向上调整大根堆,将i结点向上层移动到一个正确位置
template <class Type> void MaxHeap<Type>::FilterUp(unsigned i)
{
  if(i<1)                //检查i是否合法
    return;
  i=(CurrentSize>i)? i:CurrentSize-1;  //检查i是否大于数组长度
  int j=(i-1)/2;          //j为i的父结点
  Type temp=Heap[i];          //将i结点暂存
  while(j>0)              //若未调整至顶点
  {
    if (Heap[j]>=temp)        //若父结点小于i结点的值
      break;            //符合大根堆要求，不再调整该分支
    else              //否则
    {
      Heap[i]=Heap[j];      //将父结点的值向下移至子结点
      i=j;            //继续向上调整，i指向已移走元素的位置
      j=(i>0)?(i-1)/2:0;        //j指向i的父结点
    }
  }
  Heap[i]=temp;            //将暂存的结点插入到i位置
}

//从上而下高速大根堆，将i向下层移动至一个m结点前的正确的位置
template <class Type> void MaxHeap<Type>::FilterDown(unsigned i,unsigned m)
{
  if(m<=i||m>CurrentSize-1||i<0)    //检查i,m的合法性
    return;
  unsigned j=2*i+1;                 //定义j为i的左子结点
  Type temp=Heap[i];                //暂存可能要移动的i结点
  while(j<=m)                       //当j不超过m结点时执行循环
  {
    if(j<m&&Heap[j+1]>=Heap[j])     //j与j+1同为i的子结点，让j指向比较小的子结点
      j++;                          //优先指向右结点，这样，调整出来的堆一般是左结点小于等于右结点
    if(temp>=Heap[j])               //若:i结点不大于较小的子结点
      break;                        //符合大根堆条件，退出循环
    else                            //否则
    {
      Heap[i]=Heap[j];              //将较小的子结点移至i结点
      i=j;                          //继续调整，i指向被移走数据的子结点
      j=2*i+1;                      //j指向i的左子结点
    }
  }
  Heap[i]=temp;                     //找到了最初i结点的正确位置 ，将它插进去
}

//清空大根堆
template <class Type> void MaxHeap<Type>::MakeEmpty()
{
  CurrentSize=0;            //这样就算清空了吧...
}

//移除大根堆的顶点。并将该顶点存入Node
template <class Type> bool MaxHeap<Type>::DeleteMax(Type &Node)
{
  if(IsEmpty())                   //检查该堆是否为空堆
    return false;
  if(Node)                        //检查是否需要将最大值存入*Node
    Node=Heap[0];
  Heap[0]=Heap[--CurrentSize];    //将数组长度减1，并将最后一个元素放到堆顶点
  FilterDown(0,CurrentSize-1);    //自顶点至底层调整大根堆
  return true;
}

//插入新元素
template <class Type> bool MaxHeap<Type>::Insert(const Type Node)
{
  if(IsFull())
  {
    MaxHeapSize+=DefaultSize;
    Type *temp=new Type[MaxHeapSize];
    for(unsigned x=0;x<CurrentSize;x++)
      temp[x]=Heap[x];
    delete []Heap;
    Heap=temp;
  }
  Heap[CurrentSize]=Node;
  FilterUp(CurrentSize++);
  return true;
}

//得到最大值，即顶点
template <class Type> bool MaxHeap<Type>::GetMax(Type &Node)
{
  if(IsEmpty())            //检查该堆是否为空堆
    return false;
  else
    Node=Heap[0];          //非空堆则将最大元素赋值给Node
  return true;
}

//快速排序
template<class Type>
void QuickSort (Type a[], int p, int r)
{
  if (p<r) {
    int q=Partition(a,p,r);
  if(p<q-1)
      QuickSort(a,p,q-1); //对左半段排序
  if(q+1<r)
     QuickSort (a,q+1,r); //对右半段排序
  }
}

template<class Type>
void Swap(Type &a,Type &b)
{
  Type t=a;
  a=b;
  b=t;
}

template<class Type>
int Partition (Type a[], int p, int r)
{
  int i = p+1, j = r;
  Type x=a[p];
  while (true) {
    while ((a[i]>=x)&&(i<=r))i++;// 将>=x的元素交换到左边区域
    while ((a[j]<=x)&&(j>p))j--; // 将<=x的元素交换到右边区域
    if (i >= j) break;
    Swap(a[i], a[j]);
  }
 a[p] = a[j];
 a[j] = x;
 return j;
}

//0-1背包问题求解
#define MAXHEAP 32767

class Object{
  friend int Knapsack(int *,int *,int,int,int *);
  public:
    int operator >= (Object a) const {return (d>=a.d);}
    int operator <= (Object a) const {return (d<=a.d);}
  private:
  int ID;
  float d;
};

template <class Typew,class Typep> class Knap;
class bbnode{
  friend Knap<int,int>;
  friend int Knapsack(int *,int *,int,int,int *);
  private:
    bbnode * parent;
    bool LChild;
};

template <class Typew,class Typep>
class HeapNode{
  friend Knap<Typew,Typep>;
  public:
    operator Typep () const {return uprofit;}
  private:
    Typep uprofit,profit;
    Typew weight;
    int level;
    bbnode * ptr;
};

template <class Typew,class Typep>
class Knap{
  friend Typep Knapsack(Typep *,Typew *,Typew,int,int *);
  public:
    Typep MaxKnapsack();
  private:
    MaxHeap< HeapNode < Typew,Typep > > * H;
    Typep Bound(int i);
    void AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int level);
    bbnode * E;
    Typew c;
    int n;
    Typew *w;
    Typep *p;
    Typew cw;
    Typep cp;
    int *bestx;
};

template <class Typew,class Typep>
Typep Knap<Typew,Typep>::Bound(int i)
{
  Typew cleft=c-cw;
  Typep b=cp;
  while (i <= n && w[i] <= cleft){// n表示物品总数，cleft为剩余空间
    cleft -= w[i];//w[i]表示i所占空间
    b += p[i];//p[i]表示i的价值
    i++;
  }
  if (i <= n) b += p[i] / w[i] * cleft;// 装填剩余容量装满背包
  return b;//b为上界函数
}

template <class Typew,class Typep>
void Knap<Typew,Typep>::AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev)
{
  bbnode * b=new bbnode;
  b->parent=E;
  b->LChild=ch;
  HeapNode <Typep,Typew> N;
  N.uprofit=up;
  N.profit=cp;
  N.weight=cw;
  N.level=lev;
  N.ptr=b;
  H->Insert(N);
}

template <class Typew,class Typep>
Typep Knap<Typew,Typep>::MaxKnapsack()
{
  H=new MaxHeap <HeapNode <Typep,Typew> > (MAXHEAP);
  bestx=new int [n+1];
  int i=1;
  E=0;
  cw=cp=0;
  Typep bestp=0;
  Typep up=Bound(1);
  while(i!=n+1){// 非叶结点
    Typew wt=cw+w[i];// 检查当前扩展结点的左儿子结点
    if(wt<=c){// 左儿子结点为可行结点
      if(cp+p[i]>bestp)bestp=cp+p[i];
      AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);
    }
    up=Bound(i+1);// 检查当前扩展结点的右儿子结点
    if(up>=bestp)// 右子树可能含最优解
      AddLiveNode(up,cp,cw,false,i+1);
    HeapNode <Typep,Typew> N;//取下一个扩展节点
    H->DeleteMax(N);
    E=N.ptr;
    cw=N.weight;
    cp=N.profit;
    up=N.uprofit;
    i=N.level;
  }
  for(int j=n;j>0;j--){
    bestx[j]=E->LChild;
    E=E->parent;
  }
  return cp;
}

int Knapsack(int p[],int w[],int c,int n,int bestx[])
{
  int W=0;
  int P=0;
  Object * Q=new Object[n];

  int i;
  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)return P;
  QuickSort(Q,0,n-1);

  Knap <int,int> K;
  K.p=new int[n+1];
  K.w=new int[n+1];
  for(i=1;i<=n;i++){
    K.p[i]=p[Q[i-1].ID];
    K.w[i]=w[Q[i-1].ID];
  }
  K.cp=0;
  K.cw=0;
  K.c=c;
  K.n=n;

  int bestp=K.MaxKnapsack();
  for(i=1;i<=n;i++)
    bestx[Q[i-1].ID]=K.bestx[i];

  delete [] Q;
  delete [] K.w;
  delete [] K.p;
  delete [] K.bestx;
  return bestp;
}


void main()
{
  int n,c,i;

  ifstream fin("input.txt");
  fin>>n>>c;
  int *p=new int[n+1];
  for(i=1;i<=n;i++)fin>>p[i];
  int *w=new int[n+1];
  for(i=1;i<=n;i++)fin>>w[i];
  fin.close();

  int *x=new int[n+1];
  int b;
  b=Knapsack(p,w,c,n,x);

  ofstream fout("output.txt");
  fout<<b<<endl;
  for(i=1;i<=n;i++)fout<<x[i]<<' ';
  fout<<endl;
  fout.close();

  delete [] p;
  delete [] w;
  delete [] x;
}