//计算机0110 罗刚(20013063)
#include<iostream.h>
void Greedy(float p[],float w[],float x[],float m,int n)
{
float cu;
int i,j;
float tempP,tempW;
float total=0;
for(i=0;i<n;i++)
{
x[i]=0;
}
cu=m;
for(i=1;i<=n;i++)
{ for(j=i+1;j<=n;j++)
{
if(p[i]/w[i]<p[j]/w[j])
{
tempP=p[i];
tempW=w[i];
p[i]=p[j];
w[i]=w[j];
p[j]=tempP;
w[j]=tempW;
}
}
cout<<"p["<<i<<"]="<<p[i]<<"w["<<i<<"]="<<w[i]<<endl;
}
for(i=1;i<=n;i++)
{
if(w[i]<=cu)
{
x[i]=1;
cu=cu-w[i];
cout<<"x["<<i<<"]="<<x[i]<<endl;
//total=total+p[i]*x[i];
}
else if(cu<w[i]&&cu>0)
{
x[i]=cu/w[i];
cout<<"x["<<i<<"]="<<x[i]<<endl;
cu=0;
//total=total+p[i]*x[i];
}
else if(cu==0)
{
x[i]=0;
cout<<"x["<<i<<"]="<<x[i]<<endl;
}
//total=total+p[i]*x[i];
//cout<<"总效益值是:"<<total<<endl;
}
for(i=1;i<=n;i++)
{
total+=p[i]*x[i];
}
cout<<"总效益值是:"<<total<<endl;
}
/*void main()
{
int n=3;
float m=3;
float p[3]={3,2,1};
float w[3]={1,1,1};
float x[3]={0.0,0.0,0.0};
Greedy(p,w,x,m,n);
}*/
void main()
{
int n,i;
float m;
float p[10],w[10],x[10];
cout<<"请输入物品数量: "<<endl;
cin>>n;
cout<<"请输入背包容量: "<<endl;
cin>>m;
for(i=1;i<=n;i++)
{
cout<<"请输入第"<<i<<"个物品的效益值:"<<endl;
cin>>p[i];
cout<<"请输入第"<<i<<"个物品的的重量: "<<endl;
cin>>w[i];
}
Greedy(p,w,x,m,n);
}