贪心算法及实现
The greedy algorithm and implementation
你好我刚开始学习贪心算法，我先看了经典的换币问题。我可以理解算法中的 greediness（即，选择局部最优解以达到全局最优解。），因为我选择了硬币的最高价值，使得
总和+{所选硬币的价值}<=总价值。然后我开始在一些站点解决一些贪心算法问题。我可以解决大部分问题，但无法弄清楚 greediness 在问题中的确切应用。针对这些问题，我编写了我能想到的唯一解决方案，并得到了接受。社论也展示了解决问题的相同方法，但我无法理解贪婪范式在算法中的应用。
贪婪算法是解决特定范围问题的唯一方法吗？或者它们是解决问题的一种更有效的方法？
你能给我在应用和不应用贪心范式的情况下同样问题的伪代码吗？
我认为解决问题总是有另一种方法，但有时，正如您所说，它可能效率较低。
例如，你可以随时检查所有选项（硬币排列），存储结果并选择最好的，但是效率当然很糟糕。
希望对您有所帮助。
贪心算法只是 class 算法中的一种，迭代 construct/improve 一个解决方案。
想象一下最著名的问题 - TSP。您可以将其表述为整数线性规划问题并将其提供给 ILP 求解器，它将为您提供全局最优解（如果它有足够的时间）。但是你可以用 greedy 的方式来做。您可以构建 some 解决方案（例如，随机），然后寻找可以改进您的解决方案的更改（例如，切换两个城市的顺序），然后继续进行这些更改，直到不可能进行此类更改.
所以底线是：贪心算法只是一种有效解决难题的方法（及时，但对解决方案的质量不是必需的），但还有其他 classes 算法可以解决此类问题。
对于硬币，贪心算法也是最优算法，因此 "greediness" 不像其他一些问题那样明显。
在某些情况下，您更喜欢不是最好的解决方案，但您可以更快地计算它（例如，计算真正的最佳解决方案可能需要数年时间）。
然后你选择启发式，这应该会给你最好的结果 - 基于平均输入数据、它的结构和你想要完成的事情。
在维基百科上，找到 biggest sum of numbers in tree
有很好的解决方案
假设您在这棵树中有例如 2^1000 个节点。要找到最佳解决方案，您必须访问每个节点一次。今天的个人计算机无法在您的一生中做到这一点，因此您需要一些启发式方法。贪心算法仅需 1000 步即可找到解决方案（不超过 1 毫秒）
现实生活中有很多贪心算法的例子。一个很明显的就是找零钱的问题，要找某种货币，我们要反复发最大面额的，所以要找十七块钱六十一美分，我们发一张十块钱，一张五块钱- 美元钞票，两张一美元钞票，两个四分之一，一毛钱和一便士。通过这样做，我们可以保证最大限度地减少纸币和硬币的数量。该算法不适用于所有货币系统...more here
你好我刚开始学习贪心算法，我先看了经典的换币问题。我可以理解算法中的 greediness（即，选择局部最优解以达到全局最优解。），因为我选择了硬币的最高价值，使得 总和+{所选硬币的价值}<=总价值。然后我开始在一些站点解决一些贪心算法问题。我可以解决大部分问题，但无法弄清楚 greediness 在问题中的确切应用。针对这些问题，我编写了我能想到的唯一解决方案，并得到了接受。社论也展示了解决问题的相同方法，但我无法理解贪婪范式在算法中的应用。
贪婪算法是解决特定范围问题的唯一方法吗？或者它们是解决问题的一种更有效的方法？
你能给我在应用和不应用贪心范式的情况下同样问题的伪代码吗？
我认为解决问题总是有另一种方法，但有时，正如您所说，它可能效率较低。
例如，你可以随时检查所有选项（硬币排列），存储结果并选择最好的，但是效率当然很糟糕。
希望对您有所帮助。
贪心算法只是 class 算法中的一种，迭代 construct/improve 一个解决方案。
想象一下最著名的问题 - TSP。您可以将其表述为整数线性规划问题并将其提供给 ILP 求解器，它将为您提供全局最优解（如果它有足够的时间）。但是你可以用 greedy 的方式来做。您可以构建 some 解决方案（例如，随机），然后寻找可以改进您的解决方案的更改（例如，切换两个城市的顺序），然后继续进行这些更改，直到不可能进行此类更改.
所以底线是：贪心算法只是一种有效解决难题的方法（及时，但对解决方案的质量不是必需的），但还有其他 classes 算法可以解决此类问题。
对于硬币，贪心算法也是最优算法，因此 "greediness" 不像其他一些问题那样明显。
在某些情况下，您更喜欢不是最好的解决方案，但您可以更快地计算它（例如，计算真正的最佳解决方案可能需要数年时间）。
然后你选择启发式，这应该会给你最好的结果 - 基于平均输入数据、它的结构和你想要完成的事情。
在维基百科上，找到 biggest sum of numbers in tree
有很好的解决方案
假设您在这棵树中有例如 2^1000 个节点。要找到最佳解决方案，您必须访问每个节点一次。今天的个人计算机无法在您的一生中做到这一点，因此您需要一些启发式方法。贪心算法仅需 1000 步即可找到解决方案（不超过 1 毫秒）
现实生活中有很多贪心算法的例子。一个很明显的就是找零钱的问题，要找某种货币，我们要反复发最大面额的，所以要找十七块钱六十一美分，我们发一张十块钱，一张五块钱- 美元钞票，两张一美元钞票，两个四分之一，一毛钱和一便士。通过这样做，我们可以保证最大限度地减少纸币和硬币的数量。该算法不适用于所有货币系统...more here