bb_knapsack.cpp

分支限界背包算法实现

/*翟艳堂-200728016029033*/
/***************************************
*0-1背包问题
*在解0-1背包问题的优先队列式分支限界法中，活节点优先队列中节点元素N的优先级由该节点的上界函数Bound计算出的值uprofit给出。
*子集树中以节点N为根的子树中任一节点的价值不超过N.profit。因此用一个最大堆来实现活节点优先队列。堆中元素类型为HeapNode,
*其私有成员有uprofit,profit,weight,level和ptr。对于任意一个活节点N,N.weight是节点N所相应的重量；N.profit是N所相应的价值;
*N.uprofit是节点N的价值上界，最大堆以这个值作为优先级。子集空间树中节点类型为bbnode。
***************************************/
#include<iostream.h>
#include<stdlib.h>

template<class T>void QuickSort(T a[],int p,int r);
template<class T>int Partition(T a[],int p,int r);

template<class Typew,class Typep>
class Object
{
	/*友元函数:虽然它不是本类的成员函数，但是在它的函数体中可以通过对象名访问类的私有和保护成员*/
	friend Typep Knapsack(Typep *,Typew *,Typew,int,int *);
public:
	//重载操作符
	int operator <= (Object a) const{	return d<=a.d;	}
	int operator <	(Object a) const{	return d<a.d;	}
	int operator >=	(Object a) const{	return d>=a.d;	}
	int operator >	(Object a) const{	return d>a.d;	}
	int operator == (Object a) const{	return d==a.d;	}
private:
	int ID;
	double d;//单位重量价值
};

template<class Typew,class Typep> class Knap;
template<class Typew,class Typep>
class bbnode
{
	friend Knap<int,int>;/*声明Knap为bbnode的友元类，在Knap的成员函数中可以访问bbnode类对象的私有成员*/
	friend Typep Knapsack(Typep *,Typew *,Typew,int,int *);
private:
	bbnode* parent;	//指向父节点的指针
	bool LChild;	//左儿子节点标志
};

template<class Typew,class Typep>
class HeapNode
{
	friend Knap<Typew,Typep>;
public:
	operator Typep() const{return uprofit;}
	int operator <= (HeapNode hn) const{return uprofit<=hn.uprofit;	}
	int operator <	(HeapNode hn) const{return uprofit<hn.uprofit;	}
	int operator >= (HeapNode hn) const{return uprofit>=hn.uprofit;	}
	int operator >	(HeapNode hn) const{return uprofit>hn.uprofit;	}
	int operator == (HeapNode hn) const{return uprofit==hn.uprofit;	}
private:
	Typep uprofit,	//节点的价值上界
		profit;		//节点所相应的价值
	Typew weight;	//节点所相应的重量
	int level;		//活节点在子集中所处的层序号
	bbnode<Typew,Typep>* ptr;	//指向活节点在子集树中相应节点的指针
};
template<class Typeh>
class MaxHeap
{
public:
	MaxHeap(int n);
	void Insert(Typeh heapNode);
	void DeleteMax(Typeh &heapNode);
private:
	int size;
	Typeh *MH;
	
	void Delete(Typeh &heapNode,int index);
	void SiftUp(int index);
	void SiftDown(int index);
};
template<class Typeh>
MaxHeap<Typeh>::MaxHeap(int n)
{
	size=0;
	MH=new Typeh[n];
}
template<class Typeh>
void MaxHeap<Typeh>::SiftUp(int index)
{
	if(index<=1)
		return;
	bool done=false;
	do
	{
		if(MH[index]>MH[index/2])
		{
			Typeh tmp=MH[index];
			MH[index]=MH[index/2];
			MH[index/2]=tmp;
		}
		else
			done=true;
		index=index/2;
	}while(index>1&&!done);
}
template<class Typeh>
void MaxHeap<Typeh>::SiftDown(int index)
{
	if(2*index>size)
		return;
	bool done=false;
	do
	{
		index=2*index;
		if(index+1<=size&&MH[index+1]>MH[index])
			index=index+1;
		if(MH[index/2]<MH[index])
		{
			Typeh tmp=MH[index];
			MH[index]=MH[index/2];
			MH[index/2]=tmp;
		}
		else
			done=true;
	}while(2*index<=size&&!done);
}
template<class Typeh>
void MaxHeap<Typeh>::Insert(Typeh heapNode)
{
	size+=1;
	MH[size]=heapNode;
	SiftUp(size);
}
template<class Typeh>
void MaxHeap<Typeh>::Delete(Typeh &heapNode,int index)
{
	if(index<1||index>size)
	{
		return;
	}
	Typeh x=MH[index],y=MH[size];
	heapNode=MH[index];
	size-=1;
	if(index==size+1)
		return;
	MH[index]=y;
	if(y>=x)
		SiftUp(index);
	else
		SiftDown(index);
}
template<class Typeh>
void MaxHeap<Typeh>::DeleteMax(Typeh &heapNode)
{
	Delete(heapNode,1);
}
template<class Typew,class Typep>
class Knap
{
	friend Typep Knapsack(Typep *,Typew *,Typew,int,int *);
public:
	Typep MaxKnapsack();	//实施对子集树的优先队列式分支限界搜索
private:
	MaxHeap<HeapNode<Typep,Typew> > *H;
	Typep Bound(int i);	//计算节点所相应价值的上界
	void AddLiveNode(Typep up,Typep op,Typew cw,bool ch,int level);	//将一个新的活节点插入到子集树和优先队列中
	bbnode<Typew,Typep> *E;	//指向扩展节点的指针
	Typew c;	//背包容量
	int n;		//物品总数
	Typew *w;	//物品重量数组
	Typep *p;	//物品价值数组
	Typew cw;	//当前装包重量
	Typep cp;	//当前装包价值
	int *bestx;	//最优解:bestx[i]=1当且进当最优解含有物品i
};

/****************************************
*上界函数计算节点所相应价值的上界
****************************************/
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)
	{
		cleft-=w[i];
		b+=p[i];
		i++;
	}
	//装填剩余容量装满背包
	if(i<=n)
		b+=p[i]*cleft/w[i];
	return b;
}
/*****************************************
*将一个新的活节点插入到子集树和优先队列中
*****************************************/
template<class Typep,class Typew>
void Knap<Typep,Typew>::AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev)
{
	bbnode<Typew,Typep> *b=new bbnode<Typew,Typep>;	//生成一个新的子集树结点
	b->parent=E;
	b->LChild=ch;
	HeapNode<Typew,Typep> N;//生成一个新的最大堆节点
	N.uprofit=up;
	N.profit=cp;
	N.weight=cw;
	N.level=lev;
	N.ptr=b;
	H->Insert(N);			//将堆节点插入最大堆中
}
/******************************************
*实施对子集树的优先队列式分支限界搜索。其中假定各物品依其单位重量价值从大到小排好序。相应的排序过程可在算法的预处理部分完成。
*算法的while循环不断扩展节点，直到子集树的一个叶节点成为扩展节点时为止。此时优先队列中所有活节点的价值上界均不超过该叶结点的
*价值。因此该叶结点相应的解为问题的最优解。在while循环内部，算法首先检查当前扩展节点的左儿子节点的可行性。如果该左儿子节点是
*可行节点，则将它加入到子集树和活节点优先队列中。当前扩展节点的右儿子节点一定是可行节点，仅当右儿子节点满足上界约束时才将它
*加入子集树和活节点优先队列。
*******************************************/
template<class Typew,class Typep>
Typep Knap<Typew,Typep>::MaxKnapsack()
{
	//定义最大堆的容量为1000
	H=new MaxHeap<HeapNode<Typep,Typew> >(1000);
	//为bestx分配存储空间
	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;
}
/******************************************************
*下面的函数完成对输入数据的预处理。其主要任务是将各物品依其单位重量价值从大到小排好序。然后调用函数
*MaxKnapsack完成对子集树的优先队列式分支限界搜索。
*******************************************************/
template<class Typew,class Typep>
Typep Knapsack(Typep p[],Typew w[],Typew c,int n,int bestx[])
{
	//初始化
	Typew W=0;	//装包物品重量
	Typep P=0;	//装包物品价值
	//定义依单位重量价值排序的物品数组
	Object<Typew,Typep> *Q=new Object<Typew,Typep>[n];
	//TestB
	/*
	cout<<"1.0*p[k]/w[k]:"<<endl;
	for(int k=1;k<=n;k++)
		cout<<1.0*p[k]/w[k]<<" ";
	cout<<endl;
	*/
	//TestE
	for(int 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;//所有物品装包
	//TestB
	/*
	cout<<"Q[i].ID:"<<endl;
	for(i=0;i<n;i++)
		cout<<Q[i].ID<<" ";
	cout<<endl;
	cout<<"Q[i].d:"<<endl;
	for(i=0;i<n;i++)
		cout<<Q[i].d<<" ";
	cout<<endl;
	*/
	//TestE
	QuickSort(Q,0,n-1);//依单位重量价值非增排序
	//TestB
	/*
	cout<<"Q[i].ID:"<<endl;
	for(i=0;i<n;i++)
		cout<<Q[i].ID<<" ";
	cout<<endl;
	cout<<"Q[i].d:"<<endl;
	for(i=0;i<n;i++)
		cout<<Q[i].d<<" ";
	cout<<endl;
	*/
	//TestE
	//创建类Knap的数据成员
	Knap<Typew,Typep> K;
	K.p=new Typep[n+1];
	K.w=new Typew[n+1];
	for(i=1;i<=n;i++)
	{
		K.p[i]=p[Q[i-1].ID];
		K.w[i]=w[Q[i-1].ID];
	}
	//TestB
	//cout<<"1.0*K.p[i]/K.w[i]:"<<endl;
	//for(i=0;i<=n;i++)
	//	cout<<1.0*K.p[i]/K.w[i]<<" ";
	//cout<<endl;
	//TestE
	K.cp=0;
	K.cw=0;
	K.c=c;
	K.n=n;
	//调用MaxKnapsack求问题的最优解
	Typep bestp=K.MaxKnapsack();
	for(int j=1;j<=n;j++)
		bestx[Q[j-1].ID]=K.bestx[j];
	delete []Q;
	delete []K.w;
	delete []K.p;
	delete []K.bestx;
	return bestp;
}
template<class T>
void QuickSort(T a[],int p,int r)
{
	if(p<r)
	{
		int q=Partition(a,p,r);
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	}
}

template<class T>
int Partition(T a[],int p,int r)
{
	int i=p,j=r+1;
	T x=a[p];
	while(true)
	{
		while(a[++i]>x)
			;
		while(a[--j]<x)
			;
		if(i>=j)
			break;
		T temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
void main()
{
	//定义件数为16的物品
	int p[17]={0,16,2,5,6,8,10,5,7,11,12,9,13,17,15,14,1};//装包物品价值
	int w[17]={0,20,25,16,14,18,19,21,13,3,8,7,10,14,17,9,5};//装包物品重量
	int c=102;//背包容量
	int bestx[17];//解
	int maxP;
	int n=16;
	maxP=Knapsack(p,w,c,n,bestx);//调用算法求解
	cout<<"The max price is:"<<maxP<<endl;
	cout<<"The solution is:";
	for(int i=1;i<17;i++)
		cout<<"  "<<bestx[i];
	cout<<endl;
}