计数硬币
这个问题是通过选择尽可能少的硬币来计数到期望值,并且贪婪方法迫使算法选择最大可能的硬币。如果我们给我们提供了1、2、5和10分的硬币,并且要求我们计数18分,那么贪婪的过程将是-
- 1 - 选择一个10分硬币,剩余数量为8
- 2 - 然后选择一个5硬币,剩余数量为3
- 3 − 然后选择一个2硬币,剩余计数为1
- 4 - 最后,选择1个1分硬币解决了这个问题
虽然,这似乎工作正常,但对于此计数,我们只需要选择4个硬币。但是,如果我们稍微改变问题,则相同的方法可能无法产生相同的最佳结果。对于货币系统,如果我们有1、7、10枚硬币,则计数18枚硬币绝对是最佳选择,但对于15枚硬币,则可能会使用比必要数量更多的硬币。例如,贪婪方法将使用10 +1 + 1 +1 +1 + 1,总共6个硬币。只需使用3个硬币(7 + 7 + 1)就可以解决相同的问题
因此,我们可以得出这样的结论:贪婪的方法选择了一种立即优化的解决方案,并且在全局优化是一个主要问题时可能会失败。
例子
大多数联网算法都使用贪婪方法。这是其中一些的列表-
- 旅行推销员问题
- Prim最小生成树算法
- Kruskal的最小生成树算法
- Dijkstra的最小生成树算法
- 图-地图着色
- 图-顶点覆盖
- 背包问题
- 作业调度问题