贪心算法的组成部分
算法旨在为给定问题找到最优解。在贪心算法方法中，从给定的解空间中做出决策。由于贪婪，选择最接近看起来提供最优解的解。
贪心算法试图找到局部最优解，这最终可能导致全局最优解。但是，通常贪心算法不会提供全局最优解。
贪心算法的组成部分
贪心算法具有以下五个组成部分：
候选集 - 从此集合中创建解决方案。
选择函数 - 用于选择要添加到解决方案中的最佳候选者。
可行性函数 - 用于确定候选者是否可以用于为解决方案做出贡献。
目标函数 - 用于为解决方案或部分解决方案分配值。
解决方案函数 - 用于指示是否已达到完整解决方案。
应用领域
贪心方法用于解决许多问题，例如
使用 Dijkstra 算法查找两个顶点之间的最短路径。
使用 Prim/Kruskal 算法等在图中找到最小生成树。
贪心方法在哪里失败
在许多问题中，贪心算法无法找到最优解，此外它可能产生最差的解。旅行商问题和背包问题等问题无法使用这种方法解决。
计算硬币
此问题是通过选择尽可能少的硬币来计算到期望值，贪心方法强制算法选择尽可能大的硬币。如果我们提供了 1、2、5 和 10 元的硬币，并且我们被要求计算 18 元，那么贪婪过程将是。
选择一枚 10 元硬币，剩余计数为 8。
然后选择一枚 5 元硬币，剩余计数为 3。
然后选择一枚 2 元硬币，剩余计数为 1。
最后，选择一枚 1 元硬币解决了这个问题。
虽然看起来工作正常，但对于此计数，我们只需要选择 4 枚硬币。但是，如果我们稍微更改问题，则相同的方法可能无法产生相同的最优结果。
对于我们有 1、7、10 值硬币的货币系统，计算 18 值的硬币将是绝对最优的，但对于像 15 这样的计数，它可能使用的硬币多于必要。例如，贪心方法将使用 10 + 1 + 1 + 1 + 1 + 1，总共 6 枚硬币。而相同的问题可以通过仅使用 3 枚硬币 (7 + 7 + 1) 来解决
因此，我们可以得出结论，贪心方法选择一个立即的最优解，并且在全局优化是主要关注点的地方可能会失败。