贪心算法-------部分背包问题

问题描述

关于部分背包问题(注意不是01背包问题)，已知有5种物品和一个可容纳15kg重量的背包，每种物品的重量/价值分别为12kg/4$，2kg/2$，1kg/2$，1kg/1$和4kg/10$。假定将物品i的某一部分xi放入背包就会得到vixi的效益(0 < xi < 1, vi > 0) ，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？设计贪心策略，输出在该策略下装入背包的最大价值。`

解题思路：

首先，我们要明白部分背包问题和0/1背包问题的区别
0/1背包问题中，背包剩余容量必须要装的下物品才能取走物品，并获得价值。
部分背包问题中，背包剩余容量不足装下整个物品时。可以取走物品的部分，并根据单位价值来计算取走物品的部分的价值。
其次，贪心算法在部分背包问题中的思想体现是要尽可能的取走单位最大价值的物品。

源代码：

#include<iostream>
using namespace std;
class Bag
{
public:
	//设置一个函数计算最大价值
	double MaxValue();
private:
	//背包最大承重
	double Cost = 15;
	//v是物品价值，w是物品重量
	double v[5] = { 4,2,2,1,10 };
	double w[5] = { 12,2,1,1,4 };
	//SingleV是每件物品的单位价值
	double SingleV[5] = {};
	//TotalV是取得物品的总价值
	double TotalV=0;
};

double Bag::MaxValue()
{
	int Num1 = sizeof(v) / sizeof(v[0]);//计算数组长度
	int Num2 = 0;//作为标记
	for (int i = 0; i < Num1; i  )
	{
		SingleV[i] = v[i] / w[i];//计算每件物品的单位价值
	}
	while (Cost>0)
	{
		//找出单位最大值
		double maxv = 0;
		for (int j = 0;j < Num1;j  )
		{
			if (maxv<SingleV[j] || maxv  == SingleV[j])
			{
				maxv = SingleV[j];
				Num2 = j;//找出未取走的物品中有着最大单位价值的物品
			}
		} 
		if (Cost > w[Num2] || Cost == w[Num2])
		{
			Cost -=  w[Num2];//将物品整个加入背包
			TotalV   = v[Num2];
			SingleV[Num2] = 0;//每次取出单位最大价值物品后，将其价值置0，表示以完全取走该物品
		}
		else if(Cost < w[Num2])//当背包剩余空间不足以全部将物品装下时，装入部分物品
		{
            TotalV  = Cost*SingleV[Num2];//背包剩余容量乘于该物品的单位价值
			w[Num2]-= Cost;
			Cost = 0;//设置背包剩余容量等于0跳出while循环
		}
	}
	return TotalV;
}

int main()
{
	Bag b;
	double MaxV=b.MaxValue();
	cout << "最大价值：" << MaxV << endl;
}

结果：

这篇好文章是转载于：学新通技术网