趣学算法：贪心算法

14天阅读挑战赛

一、算法知识点

  贪心算法是“活在当下，看清楚眼前”的方法。贪心算法从问题的初始解开始，一步一步地做出当前的最好选择，逐步逼近最优解，从而尽可能地得到最优解，即使达不到最优解，也可以得到最优解的近似解。

二、例题

  有一天，阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时，远处突然出现一股烟尘，弥漫着直向上空非扬，朝他这儿卷过来，而且越来越近。靠近以后，他才看清原来是一支马队，他们公有四十人，一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋，从丛林中一支来打那个大石头跟前，喃喃地说到：“芝麻、开门吧！”，随着那个头目的喊声，大石头前突然出现一道宽阔的门路，于是强盗们鱼贯而入。阿里巴巴待在树上观察他们，直到他们走的无影无踪之后，才从树上下来。他大声喊道：“芝麻、开门吧！”，他的喊声刚落，洞门立刻打开了，他小心翼翼地走了进去，一下子惊呆了，洞中堆满了财务，还有多的无法计数的金银财宝，有的散堆在地上，有的盛在皮袋中。突然看见这么多的金银财宝，阿里巴巴深信这肯定是一个强盗们数代经营、掠夺所积累起来的宝窟。为了让乡亲们开开眼界，见识一下这些宝物，他想一种宝物只拿一个，如果太重就用锤子凿开，但毛驴的运载能力是有限的，怎么才能用驴子运走最大价值的财宝分给乡亲们呢？
  阿里巴巴陷入沉思……
  有n种物品，每个物品只有一个，第i种物品的重量为wi，价值为vi，背包的容量为W，物品可分割。如何放置物品，使得装入背包的物品价值之和最大？

三、问题分析

  如果选择价值最大的宝物，但重量非常大，也是不行的，因为运载能力是有限的；如果选重量小的物品装入，那么其价值不一定高，所以不能再总重限制的情况下保证价值最大；而每次选择单位重量价值最大的宝物，也就是说每次选择性价比（价值/重量）最高的宝物，如果可以达到运载重量m，那么一定能使得价值最大。
  由于物品是可分割的，要想物品价值最大，就得先把单位重量下价值最高的物品装入背包，接着把稍次于最高的装入，重复操作直到装满背包。

四、做题思路

  首先用结构体装载每个物品的重量、价值、性价比，用compare比较性价比，性价比高的先装入背包，solution中记录剩余容量和总价值。

五、模板代码

#include
#include

using namespace std;

struct node 
{
	double weight;
	double value;
	double cost_eff;
};

bool compare(node a, node b)
{
	return a.cost_eff > b.cost_eff;
}

double solution(int n, double W,node s[])
{
	double sum = 0;
	double surplus_capa = W;
	for (size_t i = 0; i < n; ++i)
	{
		if (s[i].weight <= surplus_capa)
		{
			surplus_capa -= s[i].weight;
			sum += s[i].value;
		}
		else
		{
			sum += s[i].cost_eff * surplus_capa;
		}
	}
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

六、算法分析

贪心算法也存在如下问题
1、不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑 ；
2、贪心算法一般用来解决求最大或最小解；
3、贪心算法只能确定某些问题的可行性范围。