基础的数据结构和算法我们基本上学完了,接下来几节,我会讲几种更加基本的算法。它们分别是贪心算法、分治算法、回溯算法、动态规划。更加确切地说,它们应该是算法思想,并不是具体的算法,常用来指导我们设计具体的算法和编码等。
贪心、分治、回溯、动态规划这4个算法思想,原理解释起来都很简单,但是要真正掌握且灵活应用,并不是件容易的事情。所以,接下来的这4个算法思想的讲解,我依旧不会长篇大论地去讲理论,而是结合具体的问题,让你自己感受这些算法是怎么工作的,是如何解决问题的,带你在问题中体会这些算法的本质。我觉得,这比单纯记忆原理和定义要更有价值。
今天,我们先来学习一下贪心算法(greedy algorithm)。贪心算法有很多经典的应用,比如霍夫曼编码(Huffman Coding)、Prim和Kruskal最小生成树算法、还有Dijkstra单源最短路径算法。最小生成树算法和最短路径算法我们后面会讲到,所以我们今天讲下霍夫曼编码,看看它是如何利用贪心算法来实现对数据压缩编码,有效节省数据存储空间的。
如何理解“贪心算法”?
关于贪心算法,我们先看一个例子。
假设我们有一个可以容纳100kg物品的背包,可以装各种物品。我们有以下5种豆子,每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大,我们如何选择在背包中装哪些豆子?每种豆子又该装多少呢?
实际上,这个问题很简单,我估计你一下子就能想出来,没错,我们只要先算一算每个物品的单价,按照单价由高到低依次来装就好了。单价从高到低排列,依次是:黑豆、绿豆、红豆、青豆、黄豆,所以,我们可以往背包里装20kg黑豆、30kg绿豆、50kg红豆。
这个问题的解决思路显而易见,它本质上借助的就是贪心算法。结合这个例子,我总结一下贪心算法解决问题的步骤,我们一起来看看。
第一步,当我们看到这类问题的时候,首先要联想到贪心算法:针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大。
类比到刚刚的例子,限制值就是重量不能超过100kg,期望值就是物品的总价值。这组数据就是5种豆子。我们从中选出一部分,满足重量不超过100kg,并且总价值最大。
第二步,我们尝试看下这个问题