0-1package.cpp

0-1背包问题的分支限界算法实现

#include <iostream.h>
struct node{//结点表结点数据结构
     node *parent;//父结点指针
     node *next;  //后继结点指针（优先队列用）
     int   level; //结点的级数
     int   tag;   //标志左右孩子
     int   cu;    //背包剩余空间
     int   pe;    //已装入物品有效益值
     int   lb;    //结点的下界值
     float ub;    //结点的上界值
};
node *head;          //活动结点队列队头
node *ANS,*E;        //解结点、根结点
int *p,*w;           //背包价值、重量数组指针
int M,lbb,cap,prof;  //背包容量、下限、剩余容量、当前价值之和
int N;               //物品数
float L;             //装入物品价值
float e,ubb;         //很小的正整数参量、价值上限
         
init(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<N;i++){
      p[i]=pp[i];
      w[i]=ww[i];
  }
  head=new(node);
  head->next=NULL;
  L=0;
  ANS=new(node);
}

LUBound(int rw,int cp,int k,int &LBB,float &UBB)
{//计算上下界限
    int i,j,c;
    LBB=cp;
    c=rw;
    for(i=k;i<N;i++){
        if(c<w[i]){
           UBB=(float)(LBB+c*p[i]/w[i]);
           for(j=i+1;j<N;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* 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 EnQueue(node *i)
{//将结点i加入优先队列
   i->next=head->next;
   head->next=i;
}
void DeQueue(node *i)
{//将结点i从优先队列中删除
   node *pre=head,*p=head->next;
   while(p!=i){
      pre=p;
      p=p->next;
   }
   pre->next=p->next;
}
node *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 Print()
{//打印结果
        int i;
        cout<<"0-1背包最优解的值为:"<<L<<endl;
        cout<<"最优解中先x=1的物品有:";
        for(i=N;i>=1;i--){
           if(ANS->tag==1){
              cout<<'X'<<i<<' ';
           }
           ANS=ANS->parent;
        }
        cout<<endl<<endl;
}
void 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;
   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<lbb-e)L=lbb-e;
           }
       }
       if(head->next==NULL){//队列空或ub>L结束
          break;
       }
       else{
          E=NextLiveNode();   //下一扩展结点
          DeQueue(E);         //将结点从队列中删除
       }
   }
   Print();
}

void main()
{
	//测试
        float e;
        int p[16]={10,12,9,15,13,12,10,14,9,7,19,18,15,12,11,10};  
        int w[16]={2,3,3,5,5,6,5,7,5,4,12,14,12,12,13,14};
        e=(float)0.0001;
		int m;
		cout << "请输入背包的重量:";
		cin >> m;
		cout << endl;
        //LcKnap *knap0=new LcKnap(p,w,100,16,e);
	    //LcKnap *knap1=new LcKnap(p,w,60,16,e);
		init(p,w,m,16,e);
		LCKNAP();       
}