#include <iostream.h>
typedef struct{
float p;
float w;
float v;
} OBJECT;
//OBJECT instance[];
void quick_sort(OBJECT instance[],int n)
{
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
if(instance[j].v>instance[i].v)
{
float temp=instance[i].w;
instance[i].w=instance[j].w;
instance[j].w=temp;
temp=instance[i].p;
instance[i].p=instance[j].p;
instance[j].p=temp;
}
}
return;
}
float knapsack_greedy (float M,OBJECT instance[],float x[],int n)
{
int i;
float m,p=0;
for (i=0;i<n;i++)
{
instance[i].v=instance[i].p/instance[i].w;
x[i]=0;
}
quick_sort(instance,n);
m=M;
for(i=0;i<n;i++)
{
if(instance[i].w<=m)
{
x[i]=1;
m-=instance[i].w;
p+=instance[i].p;
}
else{
x[i]=m/instance[i].w;
p+=x[i]*instance[i].p;
break;
}
}
return p;
}
int main()
{
float n,M,p;
cout<<"请输入物体的个数N:";
cin>>n;
OBJECT *instance=new OBJECT[n];
cout<<"请输入背包的重量M:";
cin>>M;
float *x=new float[n];
for(int i=0;i<n;i++)
{
cout<<"请输入第"<<i<<"个物体的质量和价值";
cin>>instance[i].w>>instance[i].p;
}
p=knapsack_greedy(M,instance,x,n);
cout<<"存放N个物体的价值P:"<<p;
return 0;
}