//物品类头文件
class Thing   //物品类
{       //私有数据成员
double _weight;//物品重量
double _value; //物品价值
double _dens;  //物品的价值密度,dens=value/weight
public:
//公有成员函数
void  weight(double tw)//物品重量函数,tw表示从键盘输入的物品重量
{  
_weight=tw;
}
void  value(double tv)//物品价值函数,tv表示从键盘输入的物品价值
{  
_value=tv;
}
double dens(double tw,double tv,double de )//物品的价值密度函数,de表示物品的价值密度

de=tw/tv;
_dens=de;
}

};//背包类头文件
class Bag   //背包类
{
// Thing _thing[N];  //类的组合,物品类的一个对象数组是背包类的一个数据成员
double _weighttmp;//当前方案的物品总重量
double _sumvalue; //当前方案的物品总价值
public:
//公有成员函数
// void thing[](double t[])
// {
// _thing[]=t[];
// }
Thing thing[N];
double weighttmp(double wt)
{
wt+=thing[].weight;
_weighttmp=wt;
}
double sumvalue(double sv)
{
sv+=thing[].value;
_sumvalue=sv;
}
};//主函数
#include<iostream.h>
#define N 255 //定义宏,将N的值替换为255,预定义物品最多为255件
#include"thing.h"
#include"bag.h"Thing thing[N];
typedef Bag bag,best;//定义Bag类的别名bag和best,分别用于存储当前方案和最佳方案的信息
int input(double tw,double tv)//输入物品信息函数
{
int i;
cout<<"请输入物品["<<i<<"]的重量和价值(两数以空格隔开):";
cin>>tw>>tv;
}double init()//初始化物品信息函数
{
for(int i=1;i<n;i++)
{
input(thing[i].weight,thing[i].value);      //调用输入物品信息函数,输入物品信息
thing[i].dens=thing[i].value/thing[i].weight;//价值密度dens=value/weight
}
}
int inbag() //将物品按价值密度高低放入背包
{
int i;
double weight;
do{
bag.thing[i]=thing[i];    //将物品信息存入bag类中
        bag.weighttmp+=thing[i].weight;//当前方案的背包中物品总质量
bag.sumvalue+=thing[i].value;  //当前方案的背包中物品总价值
i++;
}while(bag.weighttmp<=weightlimit);
}//结束将物品放入背包的动作
int outbag() //将当前方案中weight最大的物品从背包中取出
{
//筛选出背包中已存物品中weight最大的
double w=thing[0].weight,v=thing[0].value;
for(int j=1;j<n;j++)
{
if(w<thing[j].weight)
w=thing[j].weight;
v=thing[j].value;
else
continue;
}

bag.weighttmp-=w;//取出weight最大的物品后背包现存物品的总重量
bag.sumvalue-=v; //取出weight最大的物品后背包现存物品的总价值

}
void sort(double a[],int size) //插入排序法
{
int index;
double inserter;
for(int i=1;i<size;i++){   //共执行size-1轮
for(index=i-1,inserter=a[i];index>=0 && inserter<a[index];index--)
a[index+1]=a[index];//后挪一个位置
a[index+1]=inserter;    //插入
}
for(int j=0;j<size;j++){ //比较后输出排序结果
cout<<a[j]<<",";
}
cout<<endl;
}//主函数
void main()
{
double weightlimit;
int n;
cout<<"请输入背包限重weightlimit=";
cin>>weightlimit;  //输入背包限重
cout<<"请输入物品件数(1~255) n=";
cin>>n;  //输入物品件数
if(n>255)
cout<<"对不起,超出预定物品件数范围范围!请重新输入:";
cin>>n;
init();  //输入物品信息并对其进行初始化
double array[]=thing[n].dens;//将物品价值密度信息存入到另一个数组中
for(int i=0;i<n;i++)         //物品价值密度按原始顺序输出
cout<<array[i]<<",";
cout<<endl; 
sort(array,n); //调用排序函数,对物品按价值密度进行排序
inbag(); //将物品放入背包
do{
best=bag; //将背包中的物品信息存入暂存数组best,设置它暂时为最佳方案
outbag(); //取出背包中weight最大的物品
inbag(); //继续装物品
}while(best.sumvalue<bag.sumvalue)
cout<<"最佳方案:背包存放物品的总价值为"<<best.sumvalue<<endl; //输出最佳方案

}