本文共 1802 字，大约阅读时间需要 6 分钟。

1.问题描述

    背包问题是给定n个重量为{

    注意背包问题和0/1背包问题的区别，背包问题中，物品是可以部分装入背包的，0/1背包则不可以，要么装入，要么不装入。

2.算法思路

    贪心法求解背包问题的贪心策略是：单位价值量。因此首先将物品按照单位价值量进行递减排序，从单位价值量最大的物品开始遍历，其重量小于当前背包容量则放入，相应增加背包价值、减少背包容量；直到一个物品重量大于当前背包容量，则将其按照比例部分放入。

3.参考代码

/*贪心法求解背包问题*//*	背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn}的物品和一个容量为C的背包，	求这些物品中的一个最有价值的子集，并且要能够装到背包中每次从物品集合中选择单位重量价值最大的物品，	如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量*/#include
   
    #include
    
     using namespace std;class Good{	private:		int num;			//物品编号		double weight;	//物品重量		double value;	//物品价值 	public:		Good(int n,double w, double v);	//构造函数		Good();							//默认构造函数		void init(int n,double w,double v);	//初始化		int returnNum();		double returnWeight();		//返回重量		double returnValue();			//返回价值		friend int cmp(Good good1,Good good2);			//按照单位价值量降序		friend void KnapSack(Good *good,int num,int capacity);//贪心法求背包};//构造函数Good::Good(int n,double w, double v){	num=n;	weight=w;	value=v;}//默认构造函数Good::Good(){}//初始化void Good::init(int n,double w,double v){	num=n;	weight=w;	value=v;}//返回物品编号int Good::returnNum(){	return num;}//返回重量double Good::returnWeight(){	return weight;}//返回价值double Good::returnValue(){	return value;}//按照单位价值量降序排序int cmp(Good good1,Good good2){	return good1.returnValue()/good1.returnWeight() > good2.returnWeight()/good2.returnValue();}//贪心法求解过程void KnapSack(Good *good,int num,int capacity){	double *process=new double[num];//存放问题的解	int i;	for(i=0;i
     
      >capacity)	{		cout<<"请输入物品个数"<
      
       >good_num;		Good *good=new Good[good_num];//背包数组		//初始化物品的重量和价值		cout<<"请输入"<
       
        <<"个物品的重量和价值"<
        
         >w; cin>>v; good[i].init(i+1,w,v); } //输出用户输入的信息 cout<<"\n您输入的"<
         
          <<"个物品的信息"<
         
        
       
      
     
    
   

4.参考结果