01背包问题.cpp

算法分析中

#include<iostream>
using namespace std;

/*
使用到的知识有：
（1）友元函数的声明和定义
（2）类内部重载比较运算符
（3）快速排序
（4）优先队列（堆）的插入和删除，利用二叉排序树实现的
*/

class Object
{
public:
	friend int Knapsack( int p[], int w[], int c, int n, int bestx[] );
public:
	bool operator<=(Object a) const
	{
		return ( d >= a.d );
	};

	bool operator>=(Object a) const
	{
		return ( d <= a.d );
	};
public:
	int ID;
	float d;
	//单位重量价值
};

template< class T >
int partition(T a[], int left, int right)
{
	T temp;
	int low = left;
	int high = right;
	T v = a[left];

	while( low < high )
	{  
		while( low < high && a[high] >= v ) 
		{
			high--;
		}
		
		while( low < high && a[low] <= v ) 
		{
			low++;
		}
		
		if ( low >= high )
		{
			break;
		}

		temp = a[low];
		a[low] = a[high];
		a[high] = temp;
		low++;
		high--;
	}

	temp = a[left];
	a[left] = a[low];
	a[low] = temp;
	
	return low;
}

template< class T >
void Sort(T a[], int p, int q)
{
	if ( p >= q )
	{
		return;
	}
	int mid = partition( a, p, q);
	Sort(a, p, mid);
	Sort(a, mid + 1, q);
}

template< class Typew, class Typep > class Knap;

class bbnode
{
	friend Knap< int, int >;
	friend int Knapsack( int p[], int w[], int c, int n, int bestx[] );
public:
	bbnode* parent;
	//指向父结点的指针
	bool LChild;
	//左儿子结点坐标
};

template< class Typew, class Typep >
class HeapNode
{
	friend Knap< Typew, Typep >;
public:
	operator Typep() const
	{
		return uprofit;
	}
	bool operator<(HeapNode& a)
	{
		return uprofit>a.uprofit;
	}
	bool operator>(HeapNode& a)
	{
		return uprofit<a.uprofit;
	}
	HeapNode* operator=(const HeapNode& a)
	{
		uprofit = a.uprofit;
		profit = a.profit;
		weight = a.weight;
		ptr = a.ptr;
		level = a.level;
		return this;
	}
public:
	Typep uprofit;
	//结点的价值上界
	Typep profit;
	//结点所相应的价值
	Typew weight;
	//结点所相应的重量
	int level;
	//活结点在子集树中所处的层序号
	bbnode* ptr;
	//指向活结点在子集树中相应结点的指针
};

template<class Type>
class MaxHeap
{
	public:
		Type *H;
		int Capacity;
		int Size;
	public:
		MaxHeap(int n)
		{
			H = NULL;
			H = (Type*)malloc( sizeof( Type ) * ( n + 1 ) );
			Capacity = n;
			Size = 0;
		}
		MaxHeap( MaxHeap& a )
		{
			//要排除自赋值的情况
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[size];
				}
			}
		}

		/*
		基本的堆插入操作
		为了将node插入到堆中
		首先在下一个空闲位置++Size处，创建一个空穴，否则该堆将不是完全树
		如果x可以放在该穴中而不破坏堆的序，那么插入完成
		否则我们把空穴的父亲结点上的元素移动到该穴中，这样空穴就朝着根的方向上行一步
		继续该过程直到x能被放入空穴为止
		*/
		void Insert( Type& node )
		{
			int i;
			cout<<"Size = "<<Size<<endl;
			for( i = ++Size; H[i / 2] > node; i /= 2 )
			{
				H[i] = H[i / 2];
				if ( i / 2 == 0 )
				{
					break;
				}
			}
			H[i] = node;
			
		}

		/*
		当删除一个最小元时
		在根结点处产生一个空穴。
		由于现在堆少了一个元素，因此堆中最后一个元素必须移动到该堆的某个地方
		如果x可以放到空穴中，那么DeleteMin完成
		否则应该将两个儿子中较小者移入空穴
		这样空穴就向下推了一层。重复该步骤直到x可以被放入空穴中
		*/
		void DeleteMax( Type& node )
		{
			int i,Child;
			Type MinElement,LastElement;
			MinElement = H[ 1 ];
			LastElement = H[Size--];

			for( i = 1; i * 2 <= Size; i = Child )
			{
				Child = i * 2;
				if ( ( Child != Size && H[ Child + 1 ] < H[ Child ] ) )
				{
					Child++;
				}

				if ( LastElement > H[ Child ] )
				{
					H[ i ] = H[ Child ];      
				}
				else
				{
					break;
				}
			}
			H[i] = LastElement;
			node = MinElement;
		}
};

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

/*
上界函数Bound计算结点所相应价值的上界
也就是说装了第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] / w[i] ) * cleft;
	}
	return b;
}

/*
函数AddLiveNode将一个新的活结点插入到子集树和优先队列中
*/
template< class Typep, class Typew >
void Knap< Typep, Typew >::AddLiveNode( Typep up, Typep cp, Typew cw, bool ch, int lev )
{
	//将一个新的活结点插入到子集树和最大堆H中

	cout<<"开始插入一个结点: "<<endl;
	cout<<"up价值上界: "<<up<<endl;
	cout<<"cp当前价值: "<<cp<<endl;
	cout<<"cw当前重量: "<<cw<<endl;
	cout<<"ch是左孩子还是右孩子: "<<ch<<endl;
	bbnode* b = new bbnode;
	b->parent = E;
	b->LChild = ch;
	HeapNode< Typep, Typew > N;
	N.uprofit = up;
	N.profit = cp;
	N.weight = cw;
	N.level = lev;
	N.ptr = b;
	H->Insert(N);
}

template< class Typew, class Typep >
Typep Knap< Typew, Typep >::MaxKnapsack()
{
	//优先队列式分支限界法，返回最大价值，bestx返回最优解

	//定义最大堆容量
	H = new MaxHeap< HeapNode< Typep, Typew > >(1000);

	//为bestx分配存储空间
	bestx = new int[n+1];

	//初始化
	int i = 1;
	E = 0;
	cw = cp = 0;
	Typep bestp = 0;
	//当前最优值

	//第1个背包的价值上界
	Typep up = Bound(1);

	//搜索子集空间树
	while( i != n + 1 )
	{
		cout<<"表示层数的i是 :"<<i<<endl;
		//非叶子结点
		//检查当前扩展结点的左儿子结点
		Typew wt = cw + w[i];
		cout<<"当前扩展结点的wt :"<<wt<<endl;
		if ( wt <= c )
		{
			cout<<"开始判断左儿子结点"<<endl;
			//左儿子结点为可行结点
			if ( cp + p[i] > bestp )
			{
				cout<<"左儿子结点为可行结点"<<endl;
				cout<<"bestp is: "<<bestp<<endl;
				bestp = cp + p[i];
			}
			AddLiveNode( up, cp + p[i], cw + w[i], true, i + 1 );
		}
		up = Bound(i + 1);
		//检查当前扩展结点的右儿子结点
		cout<<"当前结点的上界是: "<<up<<endl;
		if ( up >= bestp )
		{
			cout<<"右儿子结点为可行结点"<<endl;
			//右子树可能含最优解
			AddLiveNode( up, cp, cw, false, i + 1 );
		}
		//取下一个扩展结点
		cout<<endl<<endl;
		for(int j = 0; j <= 10; ++j )
		{
			cout<<"第"<<j<<"个uprofit"<<H->H[j].uprofit<<endl;
		}
		cout<<endl;
		cout<<"取下一个扩展结点: "<<endl;
		HeapNode< Typep, Typew > N;
		H->DeleteMax( N );
		cout<<"取到的扩展结点如下: "<<endl;
		E = N.ptr;
		cw = N.weight;
		cp = N.profit;
		up = N.uprofit;
		i = N.level;
		cout<<"N.level 是: "<<i<<endl;
		cout<<"N.uprofit 是: "<<N.uprofit<<endl;
		cout<<"N.profit 是: "<<N.profit<<endl;
		cout<<"N.weight 是: "<<N.weight<<endl;	
	}

	//构造当前最优解
	for( int j = n; j > 0; --j )
	{
		bestx[j] = E->LChild;
		E = E->parent;
	}
	return cp;
}


/*
函数Knapsack完成对输入的数据的预处理。其主要任务是将各物品依其单位重量
价值从大到小排好序。然后调用函数MaxKnapsack完成对子集树的优先队列式分支限界搜索
*/
template< class Typew, class Typep >
Typep Knapsack( Typep p[], Typew w[], Typew c, int n, int bestx[] )
{
	//返回最大价值，bestx返回最优解

	//初始化
	//装包物品重量
	Typew W = 0;
	//装包物品价值
	Typep 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[i];
		W += w[i];
	}

	if ( W <= c )
	{
		return P;
		//所有物品装包
	}

	//依单位重量价值排序
	Sort< Object >(Q, 0, n);
	//创建类Knap的数据成员
	cout<<"after Sort object: "<<endl;
	for( i = 0; i <= n; ++i )
	{
		cout<<Q[i].d<<endl;
	}
	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];
		cout<<"K.p["<<i<<"] :"<<K.p[i]<<endl;
		cout<<"K.w["<<i<<"] :"<<K.w[i]<<endl;
	}
	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];
		cout<<"K.bestx["<<j<<"] :"<<K.bestx[j]<<endl;
	}
	delete []Q;
	delete []K.w;
	delete []K.p;
	delete []K.bestx; 
	cout<<"bestp is : "<<bestp<<endl;
	return bestp;
}

int main()
{
	int n = 4;
	int c = 7;
	int p[5] = { 0, 9, 10, 7, 4 };
	int w[5] = { 0, 3, 5, 2, 1 };
	int bestx[5] = { 0 };
	//Knap<int,int> nap;
	Knapsack<int,int>( p, w, c, n, bestx );
	for( int i = 0; i < 5; ++i )
	{
		cout<<bestx[i]<<endl;
	}
	return 0;
}