算法_贪心策略2

14天阅读挑战赛
参考文献 《趣学算法》 陈小玉教授
（入门书籍，对新手很友好，带你走进算法的大门

问题描述

 上一文中,我们讲到了 海盗盗窃古董的故事,相信细心的小伙伴们,已经发现了这个故事还有一些缺陷。

 此时一个海盗说道：张三，你怎么能这么想呢？ 有的古董虽小，却价值连城。怎么可以依照古董的数量，来衡量所获得的最大利益呢？

 众多海盗都觉得有点道理。

 但是问题又来了，海盗们竟然都不会数学？！ 快来帮助海盗计算计算吧，老兄！

问题梳理

	1） 问题是怎么装所获得的价值是最高的。 --- 我们最在意的就是 价值
	2） 利用贪心算法：
			① 我们就挑着重量轻的装，这样我们才能最大的程度上保证个数最多，从而价值最高。
			② 我们根据 性价比高，来进行装配，这样获取的收益最高。
			③ 我们选择价值最高的装，这样才能最大限度的获取收益。

一定要选择正确的一项，因为一旦做出了选择，将会是不可逆的。

问题分析

1. 如果我们选择了第一种方案：

   船只重量：50

如果此时按照第一种方案，那么所得利益为 ：名称： ①，②，③ –> 重量 ：10 + 30 + 20 = 50 –> 价值：30+30+40=100k
但是此时最优的选择却是，名称：④+① –> 重量 :40+10=50 –> 价值：30+80＝110ｋ．

2. 我们在来看一下第三种方案:
   （
     为啥不是第二种方案呢?
     因为第二种,是正确的.
    )
   船只重量：50

如果我们按照价值高的算。名称：④+① –> 重量：40+10=50 –> 价值：60+30=90k
如果选择的是 ①+②+③呢？重量:10+30+10=50k –> 价值：30+40+30=100k

3. 确认方案＋代码实现
   第二种方案是成立，但是我们该如何使用代码去实现呢？
   见如下：

#include <iostream>
#include <algorithm>
using  namespace std;
//古董 
struct Role
{
	double num;		//重量
	char name;		//名称 
	double mon;		//古董的价值
}; 	
//定义排序规则（按照性价比进行排序） 
bool cmp(Role a,Role b) 
{
	if(a.mon/a.num > b.mon/b.num) //降序排序 
		return a.mon/a.num > b.mon/b.num; 
	return a.num < b.num;	//如果性价比相同，则按照重量升序排序。 
} 

int main()
{
	int size; //古董的个数 
	//输入古董的个数 
	cout<<"古董的个数："<<endl;		
	cin>>size;
	struct Role r[size];	//保存古董。  
	double n = 0.0;		//海盗船的重量 
	double temp = 0.0;	//已经装入海盗船的重量
	double temp2 = 0.0; //模拟装入重量
	int size2= size;	//已经装入海盗船的个数 
	char name2[10];		//已装入海盗船古董的名称 
	
	//输入古董的名称、重量、价值 
	int i = 0;
	while(i<size) 
	{
		cout<<"请输入（"<<i+1<<"）古董名称、重量、价值"<<endl;
	    cin>>r[i].name>>r[i].num>>r[i].mon;  
		i++;
	}
	
	//输入海盗船的装量 
	cout<<"请输入海盗船的重量："<<endl;
	cin>>n;
	
	
	//因为我们采用的是贪心策略，对重量进行排序，按照从轻到重。
	sort(r,r+size,cmp);		//升序排列（从轻到重）
	int index = 0;        //下标/索引 目的: 如果依照for中i的话，如果当前元素并不符合所挑选的元素，则执行下一元素，i+1，则 上一索引中为 垃圾空间 没有元素。)

	for(int i=0;i<size;i++)		
	{ 
        temp = temp2;
		temp2 += r[i].num;	//海盗船的重量增加 
		if(temp2 >= n || i==size-1)	//超重/最后一次执行
		{
			if(temp2 > n)	//如果超重或等于船的载重 	
			{
			    temp2 = temp;    //此次不计入temp2，进入下一次
                continue;
			}else
			{	
				size2 = i+1;	//如果没有超重,则 海盗成功盗走一件. 
				name2[index++] = r[i].name;  	//装入海盗床的古董名称。
			} 
			break; 	
		}
		name2[index++] = r[i].name;  		//装入海盗船的古董名称。 
	}
	
	cout<<"海盗盗走的古董名称："<<endl; 
	
	//遍历
	for(int i = 0;i<index;i++) 
		cout<<name2[i]<<endl; 
		
	return 0;
}

按照第一个表格数据运行:

可以看到选择的是最优选择: a 和 d。

按照第二个表格数据运行：

也是最优选择 a c d。

贪心算法的缺陷

按照上面数据运行：

可以发现此时选择的是：a 和 b。

a b 总价值为31，剩余空间3，无法装入其他物品。

但是b 和 c 两个物品的总价值为 34 ＞ a+b。
总重量为 10。

所以此时的最优选择应是 b 和 c 。这是由于物品无法分割导致的

下期见咯