贪婪算法回顾：精髓就是贪

贪心算法回顾：贪心算法的本质是贪心算法吗？如果你不记得了，看完下面的例子你一定会记住的，因为这个例子太常见了，几乎到处都是用到贪心算法的地方，第1章就是一个例子，我们言归正传吧。

问题：现在有如下课程安排，尽可能多的课程安排在A教室。

首先，将所有课程安排在A老师。这是不现实的，因为有时间上的冲突。那么如何解决呢？

这个问题很难吧。算了，至少我第一次看的时候，我根本不知道。但看完下面的思路，你又会发现，啊？真有这么简单吗？

具体思路

1. 选择结束时间最早的科目，添加到A教室的第一节课中
2. 找出当前A教室的最后一节课，在下课时间之后开始的课程，有最早结束时间添加到课堂时间表A
3. 重复步骤2

经过上述步骤，得到的时间表是：

怎么样，对吧？我感觉这个算法太简单了，简单到我不敢相信最后的结果是正确的。

但是这就是贪心算法的优点，简单易实现。

贪心算法的思想是（个人理解），每一步找到当前状态的最优解，继续。

显然贪心算法并不总是能够找到最优解

来了又来了，又是一个坏例子，不过我就用它吧，哼。

问题：现在有一个小偷提着一个可以装35公斤东西的袋子。他会拿走最有价值的东西。那么贪心算法的思路如下：

1. 拿可以携带的最贵的东西 把东西放进背包
2. 重复步骤1

但如果物品如下：

1. A点：值300，重量30公斤
2. 物品B：价值200，重量20公斤
3. 物品C：价值150，重量15公斤

根据上面的思路，加载的内容是：物品A，总价值3❝但显然，如果as加载的是：物品B+物品C，总值350

此时贪心算法找不到最优解。

如果你改变主意怎么办？

1. 把最轻的东西放进去可以装在背包里
2. 重复步骤2

你会很惊讶我们发现结果是我们想要的，但是抱歉，这只是本例中的满意。

如果还有另外一个怎么办？情况？如果A项的值为500，其他条件不变怎么办？必须要深思熟虑。

其实这个例子我个人是比较相信的。这不是一个合适的例子。这类问题不适合用贪心算法来解决。但是这个例子到处都在用，所以我就用它，因为我想不出更好的例子了……

最终的结果虽然不是最优解，但也比较接近了。主要原因是算法简单

总结

贪心算法就是动态规划吗？是的，贪心算法可以说是动态规划的一个特例。也就是说，所有可以用贪心算法解决的问题都可以用动态规划来解决。但反之则不然。

其实我个人觉得贪心算法不能叫贪心算法，应该叫贪心思想，呵呵。因为它不是一个具体的算法，而是一种解决问题的思路：

每一步都会寻找当前状态的最佳解（局部最优解），最终的结果是由所有局部最优组成的全局最优解解决方案，或者接近全局最优解的解决方案

有点注重眼前利益，而不是看长远利益的感觉。这个想法听起来很简单，很容易实现，甚至简单到让人怀疑它的正确性。你的怀疑是正确的。并非每个局部最优解的组合都是全局最优解。解决方案，但优点是简单，对于上面的第一个例子，这个方法可以很好地解决。

最后是贪心算法，重点是贪婪两个字，哈哈，记住贪心算法。本质是贪