动态与贪婪算法：关于Neil G在同一主题上的回答的辩论
我试图理解动态算法和贪婪算法之间的区别，Neil G的这个回答很有帮助，但是，他发表的这一句话在评论部分引起了争论。
动态规划和贪婪算法之间的区别在于，对于动态规划，子问题是重叠的。这意味着通过“记忆”一些子问题的解决方案，你可以更快地解决其他子问题。
评论不是解决疑问的最佳场所，所以我创建了这篇文章。我的问题是：
英语不是我的母语，所以请随时纠正任何语言错误。
共有1个答案
我认为贪婪和动态解决方案之间的区别的解释并不好。贪婪的解决方案仅使用本地信息进行选择，即当前位置的最佳外观。结果，贪婪的解决方案可能“陷入”局部最优而不是全局最优。动态编程是一种技术，您可以将单个更复杂的问题分解为更简单的子问题，然后将子问题的结果组合起来，以获得初始问题的结果。解决方案既可以是贪婪的，也可以是动态的。看看我对原始线索的回答。
然而，您的声明：
If something has an optimal substructure, then all locally optimal
choices must also be globally optimal right?
错了。以 0，1 背包为例：你是一个小偷，晚上闯入某个商店。你有一个背包，它有一个固定的承重能力。商店有一些产品，每种产品都有相关的价格和重量。尽可能窃取最大的价格。
现在举个例子，你有一个容量为50的背包，价格和重量的产品分别是(21，20)，(30，22)，(22，21)和(9，9)。如果您做出局部最优的选择(即，每次您选择具有最大价格/重量比的项目)，您将选择产品(30，22)和(21，20)，而此解决方案不是最优的。最佳解决方案是取(21，20)，(22，21)和(9，9)，从而使利润增加2倍。
-
在这本书里，我用的是设计导论 然而，贪婪技术侧重于扩展部分构建的解决方案，直到您找到一个完整问题的解决方案。然后，有人说，它必须是“在这一步骤中所有可行选择中的最佳本地选择”。 由于两者都涉及局部最优性，因此其中一个不是另一个的子集吗？
-
本文向大家介绍贪婪算法相关面试题，主要包含被问及贪婪算法时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策
-
首先，是的，这是我的硬件，我觉得很难，所以我真的很感激一些指导。 我需要证明对于当
-
本文向大家介绍贪婪方法与动态规划的区别，包括了贪婪方法与动态规划的区别的使用技巧和注意事项，需要的朋友参考一下 在这篇文章中，我们将了解贪婪算法和动态编程方法之间的区别。 贪心算法 它是一种算法范式，它逐步地建立在解决方案上。选择下一步，以便它给出最明显和最直接的好处。 涉及选择局部最优值的问题将有助于选择全局最优值/问题的解决方案。这样就解决了与贪婪算法相关的问题。 不能确定贪婪算法会导致最佳解
-
以下是我需要咨询以寻求帮助的问题： 编写一个贪婪算法，使用贪婪算法以尽可能少的硬币进行兑换。您将获得一个硬币值数组和一个金额：。返回一个包含每个硬币计数的数组。 例如：应该返回数组，该数组指示每枚硬币的数量：2枚50美分硬币，1枚25美分硬币，1枚10美分硬币），没有镍币（5美分），和2便士（1美分），加起来是137美分。 从computeChange返回的数组应该与第一个参数（硬币）的长度相同。
-
有人有线索为什么它对案件2不起作用吗？非常感谢你的帮助。编辑：案例2的预期结果是6130美元。我好像得到了6090美元。