用贪婪的方法使用矩阵链
我自己在读clr，我发现很难理解一些概念。
与贪婪相比，在动态编程中，我们在全局范围内做出选择，最终得到最优解。我通过多图中最短路径的例子以及背包问题很好地理解了这些概念。
> < li>
我无法理解我们如何在Matrix Chain中动态地做出选择。我理解了递归关系，但我不会规范动态决策。(我知道它具有最优子结构特性)
如果用贪婪方法求解矩阵链算法，它将如何工作？
谢谢！
共有1个答案
这个问题不能用贪心的方法解决。
例如矩阵链[3x2]•[2x3]•[3x4]。
结果将是 （（[3x2]•[2x3]） •[3x4]） 使用贪婪方法，但最佳答案是 （[3x2]•（[2x3] •[3x4]））。
更多详情：https://www.cs.washington.edu/education/courses/421/04su/slides/matrixchain.pdf
-
本文向大家介绍贪婪算法相关面试题，主要包含被问及贪婪算法时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策
-
贪婪 vs 不贪婪 当重复一个正则表达式时，如用 a*，操作结果是尽可能多地匹配模式。当你试着匹配一对对称的定界符，如 HTML 标志中的尖括号时这个事实经常困扰你。匹配单个 HTML 标志的模式不能正常工作，因为 .* 的本质是“贪婪”的 #!python >>> s = '<html><head><title>Title</title>' >>> len(s) 32 >>> print re.
-
问题是用硬币、一角硬币、五分硬币和一便士来换零钱，并且使用最少的硬币总数。在四个面值分别是硬币、一角硬币、五分硬币和一便士的特殊情况下，我们有c1=25、c2=10、c3=5和c4=1。 如果我们只有四分之一硬币、一角硬币和一分硬币（没有五分镍币）可供使用，贪婪算法将使用六枚硬币——四分之一硬币和五便士——兑换30美分，而我们可以使用三枚硬币，即三个一角硬币。 给定一组面额，我们如何判断贪婪方法是
-
有人有线索为什么它对案件2不起作用吗？非常感谢你的帮助。编辑：案例2的预期结果是6130美元。我好像得到了6090美元。
-
以下是我需要咨询以寻求帮助的问题： 编写一个贪婪算法，使用贪婪算法以尽可能少的硬币进行兑换。您将获得一个硬币值数组和一个金额：。返回一个包含每个硬币计数的数组。 例如：应该返回数组，该数组指示每枚硬币的数量：2枚50美分硬币，1枚25美分硬币，1枚10美分硬币），没有镍币（5美分），和2便士（1美分），加起来是137美分。 从computeChange返回的数组应该与第一个参数（硬币）的长度相同。
-
任务是典型的背包问题。求解时应采用贪婪算法。我设法创建了下面的代码，但它工作得太慢了。你能告诉我怎么加快速度吗？谢谢你。 c是背包的重量限制。n表示价格权重对的数量（这两个数字都是int类型，而不是float）。限制如下：（1）如果在相同重量的元素之间选择，价格最高的元素应该被取；（2）如果在相同价格和相同重量的元素之间选择，第一个输入的元素应该被取。