贪婪法求普通背包问题

时间:2022-03-16 04:20:51

#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;
}