/*
Copyright (c) 2006, Aigui.LIU@ihep.ac.cn, 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);
}__page_break__
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; __page_break__
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;
}