gre_knap.cpp

t_xn.rar

#include<iostream.h>

int n;
int *index;
int partion(float *a,float *b,int l,int h)//一次划分
{
	int k=l,r,r0;//r用来做临时变量交换index[]中的数的时候用
	float p;
	float t0,t1;
	float t=a[k]/b[k];//求单位效益
	t0=a[k];t1=b[k];//使得t0为数组a的第一个元素，t1为数组b的第一个元素
	r0=index[k];
	l++;
	while(l<h)
	{
		while(a[l]/b[l]>t&&l<h)
			l++;
		while(a[h]/b[h]<t&&l<h)
			h--;
		p=a[l];
		a[l]=a[h];
		a[h]=p;
		p=b[l];
		b[l]=b[h];
		b[h]=p;
		r=index[l];
		index[l]=index[h];
		index[h]=r;
	}
	if(a[k]/b[k]>a[h]/b[h])
	{
		a[k]=a[h-1];
		a[h-1]=t0;
		b[k]=b[h-1];
		b[h-1]=t1;
		index[k]=index[h-1];
		index[h-1]=r0;
		return h-1;
	}
	else
	{
		a[k]=a[h];
		a[h]=t0;
		b[k]=b[h];
		b[h]=t1;
		index[k]=index[h];
		index[h]=r0;
		return h;
	}
}
void quicksort(float*a,float *b,int l,int h)
{
	int i;
	if(l<h)
	{
		i=partion(a,b,l,h);
		quicksort(a,b,l,i-1);
		quicksort(a,b,i+1,h);
	}
}
void gre_knap(float *p1,float *w1,float *p,float *w,int M,float *x,int n)
{
	int i;
	float v=(float)M;
	quicksort(p1,w1,0,n-1);//排序使得p(i)/w(i)>=p(i+1)/w(i+1)

	for(i=0;i<n;i++)
	{	
		if(w[index[i]]>v){x[index[i]]=v/w[index[i]];break;}
		x[index[i]]=1;
		v=v-w[index[i]];	
	}
	i++;
	for( ;i<n;i++)
		x[index[i]]=0;
	
}

void main()
{
	
	float*p,*w,*x,*p1,*w1;
	//p(i)为效益，w(i)为重量，x(i)为解，M为包的容量，n为物品个数
	//p'[],w1[]是为了排序的临时数组使得p1(i)为效益,w(i)为重量
	int M,i;
	cout<<"input the number of the things:n=";
	cin>>n;
	p=new float [n];
	w=new float [n];
	p1=new float [n];
	w1=new float [n];
	x=new float [n];
	index=new int [n];
	cout<<"input the contains of the knap:M=";
	cin>>M;
	for(i=0;i<n;i++)
		index[i]=i;
	cout<<"input each thing's rate:(nth p[i]) \n";
	for(i=0;i<n;i++)
	{
		cin>>p[i];
		p1[i]=p[i];
	}
	cout<<"input each thing's weight:(nth w[i])\n";
	for(i=0;i<n;i++)
	{
		cin>>w[i];
		w1[i]=w[i];
	}
	gre_knap(p1,w1,p,w, M,x, n);
//	for(i=0;i<n;i++)
////		cout<<w[i]<<"  ";
//	cout<<endl;
//	for(i=0;i<n;i++)
//		cout<<p[i]<<"  ";
//                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        	cout<<endl;
//	for(i=0;i<n;i++)
//		cout<<index[i]<<"   ";
//	cout<<endl;
	cout<<"\nthe result is:\n";
	for(i=0;i<n;i++)
		cout<<x[i]<<"  ";
	cout<<endl;
	delete p1;
	delete w1;
	delete p;delete w;delete x;

}