首页 > 编程笔记

贪心算法

算法是什么》一节讲到,算法规定了解决问题的具体步骤,即先做什么、再做什么、最后做什么。贪心算法是所有算法中最简单,最易实现的算法,该算法之所以“贪心”,是因为算法中的每一步都追求最优的解决方案。

举个例子,假设有 1、2、5、10 这 4 种面值的纸币,要求在不限制各种纸币使用数量的情况下,用尽可能少的纸币拼凑出的总面值为 18。贪心算法的解决方案如下:
可以看到,每一步都力求最大限度地解决问题,每一步都选择的是当前最优的解决方案,这种解决问题的算法就是贪心算法。

注意,虽然贪心算法每一步都是最优的解决方案,但整个算法并不一定是最优的。仍以选纸币为例,假设有 1、7、10 这 3 种面值的纸币,每种纸币使用的数量不限,要求用尽可能少的纸币拼凑出的总面值为 15,贪心算法的解决方案为:
最终贪心算法给出的解决方案是 10+1+1+1+1+1 共 6 张纸币,但是通过思考,最优的解决方案应该是只需要用 3 张纸币(7+7+1)。

总的来讲,贪心算法注重的是每一步选择最优的解决方案(又称“局部最优解”),并不关心整个解决方案是否最优。

贪心算法的实际应用

部分背包问题是使用贪心算法解决的典型案例之一,此外它还经常和其它算法混合使用,例如克鲁斯卡尔算法迪杰斯特拉算法等,我们会在后续章节一一进行讲解。

推荐阅读