/*
  Copyright (c) 2006, Computing Center of IHEP, Beijing, China
 */

//0-1背包問題優先隊列分枝限界算法
//#include "stdafx.h"
#include "iostream.h"
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<N;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<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* 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:"<<L<<endl;
        cout<<"Objects In KnapSack Are:";
        for(i=N;i>=1;i--)
        {
                if(ANS->tag==1)
                {
                        cout<<'X'<<i<<' ';
                }
                ANS=ANS->parent;
        }
        cout<<endl<<endl;
}
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;
   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);         //將結點從隊列中刪除
           }
   }//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;
}