#include "iostream"
#include "stdlib.h"
using namespace std;
/*物品的结构体*/
typedef struct
{
float p; //n个物体的价值
float w; //n个物体的重量
float v; //n个物体的价值重量比
}OBJECT;
/*贪婪法求背包问题*/
float knapsack_greeedy(float M,OBJECT instance[],float x[],int n);
/*比较函数*/
int compare(const void *elem1,const void *elem2);
void main()
{
int n; //总物体类别
int i;
float m; //背包总重量
float *x; //n个物体的分量
float p;
OBJECT *instance; //n个物体的结构体
cout<<"输入物品类数"<<endl;
cin>>n;
cout<<endl<<"输入总重量"<<endl;
cin>>m;
instance = new OBJECT[n];
x = new float[n];
cout<<endl<<"依次输入各个物品的价值和重量";
for(i=0;i<n;i++)
{
cout<<endl<<"输入第"<<i+1<<"个物品的价值和重量"<<endl;
cin>>(instance+i)->p;
cin>>(instance+i)->w;
(instance+i)->v = (instance+i)->p / (instance+i)->w;
*(x+i) = 0;
}
p = knapsack_greeedy(m,instance,x,n);
for(i=0;i<n;i++)
{
cout<<endl<<"第"<<i+1<<"价值重量比:"<<(instance+i)->v;
cout<<endl<<"第"<<i+1<<"存入背包的重量"<<(instance+i)->w * x[i];
}
cout<<"背包装的价值数："<<p;
}
int compare(const void *elem1,const void *elem2)
{
OBJECT* object1 = (OBJECT*) elem1;
OBJECT* object2 = (OBJECT*) elem2;
return object2->v - object1->v;
}
float knapsack_greeedy(float M,OBJECT instance[],float x[],int n)
{
float m,p=0;
int i;
m = M; //背包剩余重量
qsort(instance,n,sizeof(OBJECT),compare);
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;
}