贪心算法

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

举个例子，假设有 1、2、5、10 这 4 种面值的纸币，要求在不限制各种纸币使用数量的情况下，用尽可能少的纸币拼凑出的总面值为 18。贪心算法的解决方案如下：

• 率先选择一张面值为 10 的纸币，可以最大程度上减少需要拼凑的数额（剩余 8）；
• 选择一张面值为 5 的纸币，需要拼凑的数额降为 3；
• 选择一张面值为 2 的纸币，需要拼凑的数额降为 1；
• 选择一张面值为 1 的纸币，完成拼凑。

可以看到，每一步都力求最大限度地解决问题，每一步都选择的是当前最优的解决方案，这种解决问题的算法就是贪心算法。

注意，虽然贪心算法每一步都是最优的解决方案，但整个算法并不一定是最优的。仍以选纸币为例，假设有 1、7、10 这 3 种面值的纸币，每种纸币使用的数量不限，要求用尽可能少的纸币拼凑出的总面值为 15，贪心算法的解决方案为：

• 选择一张面值为 10 的纸币，需要拼凑的数额降为 5；
• 选择一张面值为 1 的纸币，需要拼凑的数额降为 4；
• 选择一张面值为 1 的纸币，需要拼凑的数额降为 3；
• 选择一张面值为 1 的纸币，需要拼凑的数额降为 2；
• 选择一张面值为 1 的纸币，需要拼凑的数额降为 1；
• 选择一张面值为 1 的纸币，完成拼凑。

最终贪心算法给出的解决方案是 10+1+1+1+1+1 共 6 张纸币，但是通过思考，最优的解决方案应该是只需要用 3 张纸币（7+7+1）。

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

贪心算法的实际应用

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