Data Structures Algorithms 简明教程
Greedy Algorithms
在所有算法方法中，最简单最直接的方法是贪心方法。在这种方法中，在不考虑当前决策未来影响的情况下，仅基于当前可用信息做出决策。
贪心算法部分地构建解决方案，以这样的方式选择下一部分，使其立即受益。此方法从不重新考虑先前做出的选择。此方法主要用于解决优化问题。贪心方法易于实现，并且在大多数情况下效率很高。因此，我们可以说贪心算法是一种启发式算法范例，它希望找到全局最优解，在每一步都遵循局部最优选择。
在许多问题中，它虽然在合理的时间内提供了近似（接近最优）的解决方案，但并不能产生最优解。
Components of Greedy Algorithm
贪心算法具有以下五个组成部分 -
-
A candidate set - 从此集合创建解决方案。
-
A selection function - 用于选择要添加到解决方案的最佳候选者。
-
A feasibility function −用于确定是否可以使用候选人来对解决方案做出贡献。
-
An objective function −用于为解决方案或部分解决方案赋值。
-
A solution function −用于指示是否已经达成完全的解决方案。
Counting Coins Problem
计数硬币问题是通过选择最少的硬币来计算所需值，而贪心法迫使算法选择最大的硬币。如果我们提供1、2、5和10的硬币，并要求我们计算18，那么贪心程序将为−
-
1-选择一枚10硬币，剩余数量为8
-
2-然后选择一枚5硬币，剩余数量为3
-
3-然后选择一枚2硬币，剩余数量为1
-
4-最后，选择一枚1硬币解决了问题
尽管它似乎工作得很好，但对于这个计数，我们只需要选择4枚硬币。但是，如果我们稍微改变一下问题，那么相同的方法可能无法产生相同的最优结果。
对于货币系统，我们有1、7、10值硬币，计算18的值硬币将是绝对最优的，但对于像15这样的计数，它可能使用的硬币比必要的还要多。例如，贪心法将使用10 + 1 + 1 + 1 + 1 + 1，总共6枚硬币。而同样的问题可以使用仅3枚硬币(7 + 7 + 1)来解决
因此，我们可以得出结论，贪心法选择了一种立即优化的解决方案，并且在整体优化是一个主要问题时可能会失败。