C++爱好者 - 网友留言

要求画出:(1)类图;(2)类中主要成员函数及友元函数流程图;(3)主函数的流程图或框图.
程序代码如下:
#include
struct node{//结点表结点数据结构
              node *parent;//父结点指针
              node *next;  //后继结点指针（优先队列用）
              int   level; //结点的级数
              int   tag;   //标志左右孩子
              int   cu;    //背包剩余空间
              int   pe;    //已装入物品有效益值
              int   lb;    //结点的下界值
              float ub;    //结点的上界值
            };
class LcKnap{//优先队列背包类
     private:
              node *head;          //活动结点队列队头
              node *ANS,*E;        //解结点、根结点
              int *p,*w;           //背包价值、重量数组指针
              int M,lbb,cap,prof;  //背包容量、下限、剩余容量、当前价值之和
              int N;               //物品数
              float L;             //装入物品价值
              float e,ubb;         //很小的正整数参量、价值上限
     public:
              LcKnap(int *pp,int *ww,int MM,int NN,float ee);//构造函数
              ~LcKnap();//析构函数
              void  LUBound(int rw,int cp,int k,int &LBB,float &UBB);//计算上下界限
              node* NewNode(node *parent,int level,int t,int cap,int prof,float ub,int lb);//生成一个新结点
              void  EnQueue(node *i);//将结点i加入优先队列
              void  DeQueue(node *i);//将结点i从优先队列中删除
               node* NextLiveNode();  //下一扩展结点
               void  Print();         //打印结果
               void  LCKNAP();        //背包问题求解
};
LcKnap::LcKnap(int *pp,int *ww,int MM,int NN,float ee)
{//构造函数
  int i;//初始化参数
  N=NN;
  M=MM;
  e=ee;
  p=new int[N];
  w=new int[N];
  for(i=0;i  {
          p[i]=pp[i];
          w[i]=ww[i];
  }
  head=new(node);
  head->next=NULL;
  L=0;
  ANS=new(node);
}
LcKnap::~LcKnap()
{//析构函数
   delete head;
   delete p;
   delete w;
   delete ANS;
}
void LcKnap::LUBound(int rw,int cp,int k,int &LBB,float &UBB)
{//计算上下界限
        int i,j,c;
        LBB=cp;
        c =rw;
        for(i=k;i        {
                if(c                {
                        UBB=(float)(LBB+c*p[i]/w[i]);
                        for(j=i+1;j                        {
                                if(c>=w[j])
                                {
                                        c=c-w[j];
                                        LBB+=p[j];
                                }
                        }
                        return;
                }
                c=c-w[i];
                LBB+=p[i];
        }
        UBB=(float)LBB;
        return;
}
node* LcKnap::NewNode(node *parent,int level,int t,int cap,int prof,float ub,int lb)
{//生成一个新结点
        node* i=new(node);
        i->parent=parent;
        i->next=NULL;
        i->level=level;
        i->tag=t;
        i->cu=cap;
        i->pe=prof;
        i->ub=ub;
        i->lb=lb;
        return(i);
}
void LcKnap::EnQueue(node *i)
{//将结点i加入优先队列
  i->next=head->next;
  head->next=i;
}
void LcKnap::DeQueue(node *i)
{//将结点i从优先队列中删除
   node *pre=head,*p=head->next;
   while(p!=i)
   {
           pre=p;
           p=p->next;
   }
   pre->next=p->next;
}
node *LcKnap::NextLiveNode()
{//下一扩展结点(取下限lb最大结点)
        node *p=head->next,*choice=p;
        int lb=p->lb;
        while(p)
        {
                if(p->lb>lb)
                {
                        choice=p;
                }
                p=p->next;
        }
        return(choice);
}
void LcKnap::Print()
{//打印结果
        int i;
        cout<<"Value Of Optimal Filling is:"<        cout<<"Objects In KnapSack Are:";
        for(i=N;i>=1;i--)
        {
                if(ANS->tag==1)
                {
                        cout<<'X'<                }
                ANS=ANS->parent;
        }
        cout<}
void LcKnap::LCKNAP()
{//背包问题求解
   int i;
   node* E=new(node);  //根结点
   E->parent=NULL;
   E->next=NULL;
   E->level=0;
   E->cu=M;
   E->pe=0;
   E->tag=0;
   LUBound(M,0,0,lbb,ubb);//计算根结点上下界限
   L=lbb-e;
   E->lb=lbb;
   E->ub=ubb;


--------------------next---------------------
while(E->ub>L)    //当前扩展结点上界<当前解时结束
   {
           i=E->level;
           cap=E->cu;
           prof=E->pe;
           if(i==N)  //解结点
           {
                   if(prof>L)
                   {
                           L=(float)prof;   //解
                           ANS=E;
                   }
           }
           else              //E有两个儿子
           {
                   if(cap>=w[i]) //左儿子可行
                   {
           EnQueue(NewNode(E,i+1,1,cap-w[i],prof+p[i],E->ub,E->lb));
                   }
           LUBound(cap,prof,i+1,lbb,ubb);  //重新计算上下界    
                   if(ubb>L)   //右儿子可行
                   {
           EnQueue(NewNode(E,i+1,0,cap,prof,ubb,lbb));
                          if(L                   }
           }
           if(head->next==NULL)//队列空或ub>L结束
           {
                   break;
           }
           else
           {
                   E=NextLiveNode();   //下一扩展结点
                   DeQueue(E);         //将结点从队列中删除
           }
   }//EndWhile
   Print();
}
//主程序
void main(int argc, char* argv[])
{
        float e;
        int p[4]={10,10,12,18},w[4]={2,4,6,9};// 4背包
        int pp[16]={10,12,9,15,13,12,10,14,9,7,19,18,15,12,11,10}; //16背包  
        int ww[16]={ 2, 3,3, 5, 5, 6, 5, 7,5,4,12,14,12,12,13,14};
        e=(float)0.0001;
        LcKnap *knap4 =new LcKnap(p,w,15,4,e);
        LcKnap *knap16=new LcKnap(pp,ww,40,16,e);
        knap4->LCKNAP();
        knap16->LCKNAP();
        delete knap4;
        delete knap16;
}


--------------------next---------------------