背包.cpp

关于分数背包的解决 欢迎批评指教

#include<iostream.h>
#include<stdlib.h>


#define max 100

typedef struct Goods
{
	int v;//value
	int w;//weigth
	float ave;//v/w
}Goods;
class package
{
public:
	void Getin();//输入数据并排序
	void sort();//排序
	void Knapsack();//执行主要任务
private:
	int n;
	int maxw;//最大体积
	Goods G[max];
};

void package::Getin()
{
	int i;
	cout<<"您需要的背包总体积:";
	cin>>maxw;
    cout<<"您需要的物品数量:";
	cin>>n;
	cout<<"请分别输入物品的价值:\n";
	for(i=0;i<n;i++) cin>>G[i].v;
    cout<<"请分别输入物品的体积:\n";
	for(i=0;i<n;i++)cin>>G[i].w;
}

void package::sort()
{
	int i,j,mark;
	Goods temp;
	for(i=0;i<n;i++) G[i].ave=(float)G[i].v/G[i].w;
	for(i=0;i<n;i++)
	{
		mark=i;//指针向下移一位
		for(j=i+1;j<n;j++)
		{
			if(G[j].ave>G[mark].ave)mark=j;
		}
		if(mark!=i){
    		temp.ave=G[mark].ave;
	    	temp.v=G[mark].v;
	    	temp.w=G[mark].w;

    		G[mark].ave=G[i].ave;
	    	G[mark].v=G[i].v;
    		G[mark].w=G[i].w;

    		G[i].ave=temp.ave;
    		G[i].v=temp.v;
    		G[i].w=temp.w;
		}
	}
}

void package::Knapsack()
{
	int i,total=0;
	float t;
	float temp=0;
	sort();
	for(i=0;i<n;i++)
	{   		   
		if(total+G[i].w>maxw)//超过了
		{
			t=(float)(maxw-total)/G[i].w;
			cout<<"第"<<i+1<<"次"<<"放入价值为:"<<G[i].v <<"体积为:"<<G[i].w<<"物品的"
				<<maxw-total<<"/"<<G[i].w<<endl;
			temp+=t*G[i].v;
			cout<<"该背包能放入的最大价值是:"<<temp<<endl;
			i=n+1;
		}
		else 
		{   cout<<"第"<<i+1<<"次"<<"放入价值为:"<<G[i].v <<"体积为:"<<G[i].w<<"物品\n";
			total+=G[i].w;
			temp+=G[i].v;
		}
	}
  }

void main(void)
{
	package g;
	g.Getin();
	g.Knapsack();
}