我试图理解动态算法和贪婪算法之间的区别，并且这个答案由Neil G很有帮助 https://stackoverflow.com/a/13713735/2715083但是，他的一句话却引起了评论区的热议。
动态规划和贪心算法之间的区别在于，动态规划的子问题是重叠的。这意味着通过“记住”某些子问题的解决方案，您可以更快地解决其他子问题。
评论不是解决疑问的最佳场所，所以我创建了这篇文章。我的问题是：
最小生成树具有最优子结构以及重叠子问题。此外，在 MST 中，局部最优选择就是全局最优。因此，动态属性和贪婪属性都成立，对吗？上面引用的部分如何证明这一点？
最优子结构的性质与“局部最优然后全局最优”的性质有何不同？我的头在转：如果某物具有最优子结构，那么所有局部最优选择也一定是全局最优的，对吗？有人可以解释一下我哪里出了问题吗？
英语不是我的母语，所以请随时纠正任何语言错误。
我认为对贪婪解决方案和动态解决方案之间差异的解释不好。贪婪的解决方案仅使用本地信息（即当前位置看起来最好的信息）进行选择。因此，贪婪的解决方案可能会“陷入”局部最优而不是全局最优。动态规划是一种将单个更复杂的问题分解为更简单的子问题的技术，然后组合子问题的结果以获得初始问题的结果。解决方案可以是both贪婪且动态。看看我对原始线程的回答。
然而你的这个声明：
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。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
