贪婪算法及其实现

Question

你好，我刚刚开始学习贪婪算法，我首先看了经典的硬币变化问题。我可以理解算法中的贪婪（即，选择局部最优解以实现全局最优），因为我选择硬币的最高价值，使得总和{所选硬币的价值}

贪婪算法是解决特定范围问题的唯一方法吗？或者它们是解决问题的一种更有效的方式？

你能给我同样问题的伪代码吗？

Answer 1

贪婪算法只是一类迭代构建/改进解决方案的算法。

想象一下最著名的问题——TSP。你可以将其公式化为整数线性规划问题，并将其交给ILP求解器，它会给你全局最优解(如果有足够的时间)。但是你可以用贪婪的方式去做。你可以构建一些解决方案(例如，随机地)，然后寻找改进你的解决方案的改变(例如，交换两个城市的顺序),你继续做这些改变，直到不可能有这样的改变。

因此，底线是：贪婪算法只是一种有效解决难题的方法（及时，但在解决方案的质量上不是必需的），但还有其他类别的算法可用于解决此类问题。

Answer 2

我认为总有另一种方法可以解决问题，但有时，正如你所说，它可能会效率降低。

例如，您可以随时检查所有选项（硬币排列），存储结果并选择最佳选项，但效率当然很糟糕。

希望有帮助。

Answer 3

现实生活中有很多贪婪算法的例子。其中一个明显的例子是硬币兑换问题，为了在某种货币上找零，我们重复分配最大面额，因此，为了给出17美元61美分的零钱，我们给出一张10美元的钞票，一张5美元的钞票，两张1美元的钞票，两张25美分的钞票，一毛钱和一便士的钞票。通过这样做，我们保证最小化钞票和硬币的数量。这个算法并不适用于所有的货币系统…更多