第2章 贪心算法

我们首先来学习一种简单的算法——贪心算法，“贪心”又名“贪婪”，是求解最优化问题的一种方法，生活中有很多使用“贪心”的例子，例如，吃水果时选最大的，旅游时选最好玩的地方，吃饭时点最好吃的菜。因此在求解最优问题时，贪心算法是最直观和最容易理解的。但是事物总是存在两面的，当前的最优并不一定是最终结果的最优，贪心算法并不能保证有最佳答案，而是常常帮助我们得到接近于最佳的答案。

本章主要涉及的知识点如下。

● 短浅的眼光——贪心：学会贪心思想的本质及贪心算法的优缺点。

● 美丽心灵——哈夫曼编码：通过电影《美丽心灵》的编码问题，学会使用贪心算法进行哈夫曼编码。

● 带你去旅行——单源最短路径：通过实际生活中的旅行问题，学会使用贪心算法规划旅游路径。

● 选择困难症——背包问题：通过装背包的问题，学会使用贪心算法将尽可能多的物品装进背包。

● 搬家师傅的烦恼——集装箱装载问题：结合实际生活中的搬家问题，学会使用贪心算法进行搬家。

注意：贪心算法是求解最优问题的一种思路。