使用动态规划或贪心方法解决问题？
问题应该具有哪些属性，以便我可以决定使用动态规划或贪婪方法？
What properties should the problem have so that I can decide which method to use dynamic programming or greedy method?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
动态规划问题表现出最优子结构。这意味着问题的解可以表示为严格较小的子问题的解的函数。
此类问题的一个示例是矩阵链乘法。
仅当局部最优选择导致完全最优解时才能使用贪心算法。这可能很难立即看到，但通常更容易实现，因为您只需要考虑一件事（贪婪的选择）而不是多件事（所有较小子问题的解决方案）。
一种著名的贪婪算法是用于查找最小生成树的Kruskal 算法。
Dynamic programming problems exhibit optimal substructure. This means that the solution to the problem can be expressed as a function of solutions to subproblems that are strictly smaller.
One example of such a problem is matrix chain multiplication.
Greedy algorithms can be used only when a locally optimal choice leads to a totally optimal solution. This can be harder to see right away, but generally easier to implement because you only have one thing to consider (the greedy choice) instead of multiple (the solutions to all smaller subproblems).
One famous greedy algorithm is Kruskal's algorithm for finding a minimum spanning tree.
Cormen、Leiserson、Rivest 和 Stein 的算法书的第二版有一个标题为“贪婪方法的理论基础”的章节 (16.4)，讨论贪婪方法何时产生最佳解决方案。它涵盖了许多具有实际意义的案例，但并非所有产生最佳结果的贪婪算法都可以用该理论来理解。
我还发现了一篇题为“从动态编程到贪婪算法”的论文，链接为 这里讨论的某些贪心算法可以看作是动态规划的细化。快速浏览一下，您可能会感兴趣。
The second edition of Cormen, Leiserson, Rivest and Stein's Algorithms book has a section (16.4) titled "Theoretical foundations for greedy methods" that discusses when the greedy methods yields an optimum solution. It covers many cases of practical interest, but not all greedy algorithms that yield optimum results can be understood in terms of this theory.
I also came across a paper titled "From Dynamic Programming To Greedy Algorithms" linked here that talks about certain greedy algorithms can be seen as refinements of dynamic programming. From a quick scan, it may be of interest to you.
确实有严格的规则要知道。正如有人已经说过的，有些事情应该亮起红灯，但最终只有经验才能告诉你。
There's really strict rule to know it. As someone already said, there are some things that should turn the red light on, but at the end, only experience will be able to tell you.
当可以根据每个阶段可用的局部信息做出决策时，我们应用贪婪方法。我们确信遵循每个阶段的决策集，我们将找到最优解决方案。
然而，在动态方法中，我们可能不确定在一个阶段是否做出决策，因此我们进行一组可能的决策，其中一个可能的元素可能会产生解决方案。
We apply greedy method when a decision can be made on the local information available at each stage.We are sure that following the set of decisions at each stage,we will find the optimal solution.
However, in dynamic approach we may not be sure about making a decision at one stage, so we carry a set of probable decisions , one of the probable elements may take to a solution.