friend.cpp

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

template<class Typew,class Typep>
class Object{
	friend Typep Knapsack(Typep*,Typew*,Typew,int);

	public:
		int operator<(Object<Typew,Typep> a) const//重载小于运算符号
		{
			return (d<a.d);
		}

	private:
		int ID;
		float d;

};



//定义两个类的友元函数
template<class Typew,class Typep>
Typep Knapsack(Typep p[],Typew w[],Typew c,int n)
{
	//为Knap::Backtrack初始化

	Typew W=0;
	Typep P=0;

	Object<Typew,Typep>*Q=new Object<Typew,Typep>[n];
	
	int i;

	for(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(Q,n);


//	for(i=0;i<n;i++)
//		cout<<Q[i].ID<<Q[i].d<<" ";
//	cout<<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];

	}

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

	//回溯搜索
	K.Backtrack(1);

	delete[] Q;
	delete[] K.w;
	delete[] K.p;
	



	return K.bestp;
}