object.cpp

计算机算法设计与分析(王晓东)教材上相关源程序代码。 包括分治法(4)

#include "iostream.h"
#include "Maxheap.h"


void swap(int &a, int &b);

void sort(int a[],int n);

int Knapsack(int p[],int w[],int,int n,int bestx[]);


/*********************object*********************************/
/*
用于计算上界时的物品单位重量价值的预排序
*/

class Object{
	friend int  Knapsack(int p[],int w[],int,int n,int bestx[]);
	public:
		int operator<=(Object a)const
		{return (d<=a.d);}
	private:
		int ID;
		float d;//单位重量价格
};


/*********************bbnode*********************************/
/*
子集空间树中的结点类型为bbnode。
*/
class bbnode{
	friend class Knap;
	friend int Knapsack(int *,int *,int,int,int *);
	private:
		bbnode*parent; //指向父结点的指针
		bool LChild;//左儿子结点标志
};

/*********************bbnode*********************************/
/*
子集树中以结点N为根结点的子树中任一
结点的价值不超过N.uprofit。可以使用一个最大堆来实现活结点优先队列。
堆中元素类型为HeapNode，其私有成员有uprofit,profit,weight和level。
对于任意结点N，N.weight是结点N所相应的重量；N.profit是N所相应的价值；
N.uprofit是结点N的价值上界，最大堆以这个值作为优先级。
*/
class HeapNode{
	friend class Knap;
	public:
		operator float() const{return uprofit;}
	private:
		float uprofit;//结点的价值上界，优先级
		int	  profit;//结点所相应的价值
		int weight;//结点所相应的重量
		int level;//活结点在子集树中所处的层序号
		bbnode *ptr;//指向活结点在子集树中相应结点的指针
};


class Knap{
	friend int Knapsack(int *,int *,int,int,int *);
	public:
		int MaxKnapsack();
	private:
		MaxHeap<HeapNode> *H;
		float Bound(int i);
		void AddLiveNode(float up,int cp,int cw,bool ch,int level);
		bbnode * E;//指向扩展结点的指针
		int c;//背包容量
		int n;//物品总数
		int * w;//物品重量数组
		int * p;//物品价值数组
		int cw;//当前背包容量
		int cp;//当前背包价值
		int * bestx;//最优解
};


float Knap::Bound(int i)
{//计算结点所相应价值的上界
	int cleft = c-cw;
	float b = cp;
	
	while(i<=n && w[i]<=cleft){
		cleft -=w[i];
		b = b + w[i];
		i++;
	}

	//
	if(i<=n) b = b + 1.0*p[i]/w[i]*cleft;
	return b;
}



void Knap::AddLiveNode(float up,int cp,int cw,bool ch,int level)
{
	bbnode * b = new bbnode;
	b->parent = E;
	b->LChild = ch;
	HeapNode  N;
	N.uprofit = up;
	N.profit = cp;
	N.weight = cw;
	N.level = level;
	N.ptr = b;
	H->Insert(N);
}


int Knap::MaxKnapsack()
{
	H = new MaxHeap<HeapNode>(1000);

	bestx = new int[n+1];

	int i = 1;
	E = 0;
	cw = cp = 0;
	int bestp = 0;
	float up = Bound(1);
	
	while(i!=n+1)
	{

		int 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);
			cout<<"加入左儿子后的堆："<<endl;
			H->print();
		}

		up=Bound(i+1);
		if(up > bestp)
		{
			AddLiveNode(up,cp,cw,false,i+1);
			cout<<"加入右儿子后的堆："<<endl;
			H->print();
		}

		HeapNode N; 
		H->DeleteMax(N);
		cout<<"删除堆中最大值后："<<endl;
		H->print();

		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;
}



void swap(Object &a, Object &b)
{
	Object temp=a;
	a=b;
	b=temp;
}


void sort(Object a[],int n)
{
	int i,j;
	int k;
// T temp;
	for(i=0;i<n-1;i++)
	{
		k=i;
		for(j=i+1;j<n;j++)
		{
			if(a[k]<=a[j])//改动了！！
				k=j;
		}
		//temp=a[k];
		//a[k]=a[i];
		//a[i]=temp;
		swap(a[k],a[i]);
	}
}



int Knapsack(int p[],int w[],int c,int n,int bestx[])
{
	int W = 0;
	int P = 0;

	Object * Q = new Object[n];
	for(int i = 1; i<=n; i++)
	{
		Q[i-1].ID = i;
		Q[i-1].d = 1.0*p[i]/w[i];
		P = P + p[i];
		W = W + w[i];
	}
	

	sort(Q,n);

	Knap K;
 
	K.p = new int[n+1];
	K.w = new int[n+1];	
	for(i = 1; i<= n; i++)
	{
		K.p[i] = p[Q[i-1].ID];
		K.w[i] = w[Q[i-1].ID];
	}

	K.cp = 0;
	K.cw = 0;
	K.c = c;
	K.n = n;

	int 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;
}




void main()
{	
	int n = 4;
	int c = 40;
	int w[5]={0,16,15,10,14};
	int p[5] = {0,45,25,30,15};
	int bestx[5];
	//int cp;

	int cp = Knapsack(p,w,c,n,bestx);

	cout<<"最大效益："<<cp<<endl;
	cout<<"所选择的物品："<<endl;
	for(int i = 1;i<=n;i++)
	{
		cout<<bestx[i]<<",";	
	}
}


/************************************MaxHeap************************************/

template<class T>
bool MaxHeap<T>::Insert(const T& x){
	if(IsFull()) {
		cerr<<"Heap Full!"<<endl;
		return false;
	}
	heap[currentSize] = x;
	FilterUp(currentSize);
	currentSize++;
	return true;
}

template<class T>
void MaxHeap<T>::print(){
	if(IsEmpty()) {
		cerr<<"Heap Empty!"<<endl;
	}
	else
	{
		for(int i=0;i<currentSize;i++)
		{
			cout<<heap[i]<<",";
		}
		cout<<endl;
	}
}

template<class T>
MaxHeap<T>::MaxHeap(int ms):defaultSize(100){
	 maxSize = ms > defaultSize ? ms : defaultSize;
	 heap = new T[maxSize];
	 currentSize = 0;
}

template<class T>
MaxHeap<T>::MaxHeap(T a[],int n):defaultSize(100)
{
	//用一个数组来初始化堆
	maxSize = n > defaultSize ? n : defaultSize;
	heap = new T[maxSize];
	currentSize = n;
	for(int i = 0; i < n; i++)
		heap[i] = a[i];
	int curPos = (currentSize - 2) / 2;
	
	while(curPos >= 0){
		FilterDown(curPos,currentSize - 1);
		curPos--;
	}
}

template<class T>
MaxHeap<T>::~MaxHeap(){
	delete []heap;
}

template<class T>
void MaxHeap<T>::FilterDown(const int start,const int endOfHeap){
	//自顶向下进行调整，将start节点放至对应的位置
	int i = start,j = i * 2 + 1;//start的左子树
	T temp = heap[i];
 
	while(j <= endOfHeap){
		if(j < endOfHeap && heap[j] < heap[j+1]) j++;//如果左右子树都存在，找出较大者，用j标记      
		if(temp > heap[j]) break;//找到了相应的位置
		else{
			heap[i] = heap[j];
			i = j;
			j = 2 * i + 1;
			}

	}
	
	heap[i] = temp;
}

template<class T>
void MaxHeap<T>::FilterUp(const int start){
	//自底向上进行调整，将start节点放至对应的位置
	int i = start, j = ( i - 1 ) / 2;//父节点的编号
	T temp = heap[i];
	while(i > 0){
		if(temp <= heap[j]) break;//找到了相应的位置
		else{
			heap[i] = heap[j];
			i = j;
			j = (i - 1) / 2;
		}
	}
	heap[i] = temp;
}

template<class T>
bool MaxHeap<T>::DeleteMax(T &x){
	if(IsEmpty()){
		cerr<<"Heap empty!"<<endl;
		return false;
	}
	x = heap[0];
	heap[0] = heap[currentSize - 1];
	currentSize--;
	FilterDown(0,currentSize-1);
	return true;
}

template<class T>
bool MaxHeap<T>::IsEmpty(){
	return currentSize == 0;
}
 
template<class T>
bool MaxHeap<T>::IsFull(){
	return currentSize == maxSize;
}

template<class T>
void MaxHeap<T>::MakeEmpty(){
	currentSize = 0
}