贪婪算法
在本教程中，您将学习什么是贪婪算法。 此外，您还会找到一个贪婪方法的示例。
贪心算法是一种通过选择当前可用的最佳选项来解决问题的方法，而无需担心将来会带来什么结果。 换句话说，本地最佳选择旨在产生全局最佳结果。
对于所有问题，该算法可能都不是最佳选择。 在某些情况下，它可能会产生错误的结果。
该算法永远不会返回来扭转所做出的决定。 该算法以自顶向下的方式工作。
该算法的主要优点是：
- 该算法更容易描述。
- 与其他算法相比，该算法的性能更好（但并非在所有情况下）。
可行的解决方案
一种可行的解决方案是为问题提供最佳解决方案的解决方案。
贪婪算法
- 首先，解决方案集（包含答案）为空。
- 在每个步骤中，将一个项目添加到解决方案集中。
- 如果解决方案集可行，则保留当前项目。
- 否则，该项目将被拒绝，不再考虑。
贪婪方法示例
Problem: You have to make a change of an amount using the smallest possible number of coins.
Amount: $28
Available coins:
$5 coin
$2 coin
$1 coin
解决方案：
- 创建一个空的
solution-set = {}。 coins = {5, 2, 1}sum = 0- 当
sum≠38时，请执行以下操作。 - 从
coins中选择一个硬币C，使得sum + C < 28。 - 如果
C + > 28之和，则不返回任何解。 - 否则，
sum = sum + C。 - 将
C添加到solutionSet中。
在前 5 次迭代之前，解决方案集包含 5 个 5 美元个硬币。 之后，我们得到 1 个 2 美元硬币，最后得到 1 个 1 美元硬币。