在接触编程之初，我就听到了一个名词：“贪心算法“。什么？算法也有贪心的？于是带着这份好奇，查阅了一些资料。一段时间之后，豁然开朗。原来计算机的世界里面，除了有舍己顾大局的英勇战士，还有处处斤斤计较的贪心小坏蛋。不过计算机的世界跟现实世界一样，贪心小坏蛋有时候可是有大作用，让我们娓娓道来，揭示这个贪心小坏蛋的好的一面。

贪心三步走

小坏蛋的贪心是有原则的。

第一， 明确什么是最优解？小本本记下来先。

第二， 明确什么子问题的最优解？再用小本本记下来。

第三， 分别求出所有子问题的最优解，再堆叠出整体的最优解？问题解决，小本本可以不用记了。

不懂？ 让我们举个例子

背包问题：

有一个背包，最多能承载150斤的重量，现在有7个物品，重量分别为[35, 30, 60, 50, 40, 10, 25]，它们的价值分别为[10, 40, 30, 50, 35, 40, 30]，问：如何选择才能使得在背包得承重范围内背走最多价值得物品？

我们的贪心小坏蛋一看，立马遵照自己的贪心三步走原则，分析起来：

1、 什么是最优解：在重量限制范围内，价值最大

2、 什么是子问题的最优解：每次选择当前价值最高得物品

3、 分别求出所有子问题的最优解：[4、2、6、5]，总重：130，总价值165

可以看到总重量只有130斤，我们的背包足足150斤的承重，剩下20斤岂不是浪费，于是贪心小坏蛋决定换一个角度分析：

1、 什么是最优解：在重量限制范围内，重量最小

2、 什么是子问题的最优解：每次选择当前重量最小的物品

3、 分别求出所有子问题的最优解：[6、7、2、1、5]，总重：140，总价：155

这个时候背包多用了10斤的承重，装下了比之前更重的东西，奈何其中有些东西不是很值钱呀，典型的得不偿失。小坏蛋灵机一动，既然如此，何不选择一些既轻又值钱的东西呢？于是小坏蛋把以上物品的重量与价值做了一个比值,分别求出每一个物品的单位重量具有的价值，毕竟一斤的黄金肯定比一斤的银更值钱。得到以下结果：[ 0.285、1.333、0.5、1、0.875、4、1.2]，于是从这个角度分析：

1、 什么是最优解：在重量限制范围内，价值密度最高

2、 什么是子问题的最优解：每次选择当前价值密度最高的物品

3、 分别求出所有子问题的最优解：[6、2、7、4、1]，总重：150，总价170

最终，贪心的小坏蛋使用最后一个方法，满载而归。

最后，我们分析一下，贪心算法的思维，到底贪在哪里，如何贪才能获得最好的结果。可以看出，在贪心三步走的第一第二步，贪心算法都是用局部的眼光来看待问题，只取当前最好的选择，丝毫不会想着后面的步骤该怎么办。其次，如何贪才能获得最好的结果，这个需要具体问题具体分析。这个背包问题想要贪得最多，从结果看来价值密度这个角度是最好的。但是并不排除还有一些问题，从价值这个角度来分析，结果是贪得最多的。例如，不限制背包的容量，只限制背包能装物品的个数。那么此时，从价值密度的角度来分析显然比不上从价值的角度分析。因为此时，我们只需要考虑选价值最多的物品，而不需要考虑重量了。

贪心的思维，在人工智能领域也大放异彩。围棋AI，Alpha Go，就是建立在贪心的思维上。因为围棋的特殊性，计算机无法计算出围棋的所有排列，于是科学家就用贪心算法的思维，只求每一步的最优解，最终达到全局最优的目的。学习上也是如此，当问题过于复杂过于庞大，不妨也尝试只做个贪心的小坏蛋，今天最优秀，明天最优秀，那么天天你都是最优秀的。开玩笑，但也要量力而行不是。