sort.h

回朔解决0-1背包,里面有VC++的代码,可供大家参考,如里有误的,请和我联系

void Swap(Object &a,Object &b)
{
	Object temp;
	temp.d=a.d;temp.ID=a.ID;
	a.d=b.d;a.ID=b.ID;
	b.d=temp.d;b.ID=temp.ID;
}
int Partition(Object *a,int p,int r)
{
	int i=p,j=r+1;
	Object x=a[p];
	while(true)
	{
		while(a[++i].d<x.d);
		while(a[--j].d>x.d);
		if(i>=j)break;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
void QuickSort(Object *a,int p,int r)
{
	if(p<r)
	{
		int q=Partition(a,p,r);
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	}
}
void Sort(Object *a,int n)
{
   QuickSort(a,0,n-1);
}
float Knapsack(float p[],float w[],float c,int n)
{
	float W=0;
	float P=0;
	Object *Q=new Object[n];
	for(int i=1;i<=n;i++)
	{
		Q[i-1].ID=i;
		Q[i-1].d=(float)(1.0*p[i])/w[i];
		cout<<"Q[i-1].d="<<Q[i-1].d<<endl;
		P+=p[i];
		W+=w[i];
	}
	if(W<=c)return P;
	Sort(Q,n);
	cout<<endl;
	cout<<"out"<<endl;
	Knap K;
	K.p=new float [n+1];
	K.w=new float [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;
}