背包问题.cpp

内有6个源程序代码,均为数据结构的实现代码

#include"iostream.h"
#include"stdlib.h"
#include"stdio.h"
#define N 20
class goods{
public:
	float c;
	float v;
	float p;
};
void main()
{
	goods a[N],t;
	int n;
	cout<<"Please input the number of the goods:";
	cin>>n;
	cout<<"Pleade input the countity and value:"<<endl;
	for(int i=0;i<n;i++)
		cin>>a[i].c>>a[i].v;
	for(i=0;i<n;i++)
		a[i].p=a[i].v/a[i].c;
	for(i=0;i<n;i++)
		for(int j=i;j<n-1;j++)
			if(a[j].p<a[j+1].p||(a[j].p==a[j+1].p&&a[j].c<a[j+1].c))
			{
				t.c=a[j].c;
				t.v=a[j].v;
				t.p=a[j].p;
				a[j].c=a[j+1].c;
				a[j].v=a[j+1].v;
				a[j].p=a[j+1].p;
				a[j+1].c=t.c;
				a[j+1].v=t.v;
				a[j+1].p=t.p;
			}
			float maxvalue=0,bestcountity=0;
			i=0;
			while(bestcountity<10&&i<n)
			{
				if(bestcountity+a[i].c<=10)
				{
					bestcountity+=a[i].c;
					maxvalue+=a[i].v;
					cout<<i<<"  ";
					cout<<"The quantity is:"<<a[i].c<<" ";
					cout<<"The value is:"<<a[i].v<<" ";
					cout<<a[i].p<<" ";
				}
				cout<<endl;
				i++;
			}
			cout<<"The max value is:"<<maxvalue<<endl;
			cout<<"The best countity is:"<<bestcountity<<endl;
}