贪心算法还是动态规划？
给出了列表l= x_1，...，x_n。列表中的每个元素都是一块木头的长度。要粘合两块木头，长度a和b，你需要胶水的最大值(a，b)。在粘合之后，你得到一块长度为a+b的木头。计算胶水的最小用量来粘合所有的木块。
你认为贪婪算法在这里行得通吗？我想不出任何例子。说贪婪算法我的意思是:取两个最小长度的片段，将它们粘合在一起，直到所有的片段都粘合在一起。使用一些优先级队列，这可以在O(n log n)复杂度内完成。
这行得通吗？如果没有，请给我一些列表l的例子，它可以粘合在比贪婪算法所说的更少的胶水中。
回答 3
Stack Overflow用户
发布于 2016-01-13 06:48:41
贪婪算法并不总是最优的。一个相反的例子是1，2，2，3，贪婪算法将使用10个单位的胶水，而最优算法将使用9个单位。
贪心算法：
1-2 = 2 glue
2-3 = 3 glue
3-5 = 5 glue
---------------
total = 10 glue最优：
2-2 = 2 glue
1-3 = 3 glue
4-4 = 4 glue
--------------
total = 9 glue这就是动态编程。
Stack Overflow用户
发布于 2016-01-13 23:59:56
看起来好像有，没有最优的贪婪算法和，没有通用的动态规划解。我认为这是NP-hard，我解释了原因。
让我们来分析问题。我们有N个元素。让我们将这个集合分成两个具有X和Y元素的子集。首先，我们粘合X子集的所有元素，然后以某种方式粘合Y子集的所有元素(就像分而治之的技术)。在最后一次粘合中，我们应该粘合代表X和Y子集的2个元素。在最后一次粘合中，我们需要的最小胶量是多少？当X元素和Y元素之和的差值最小时！我们将这个问题表示为递归划分问题，它本身就是NP难的
Stack Overflow用户
发布于 2020-05-28 15:43:52
贪婪算法肯定不会像Briguy37说的那样工作，因为贪婪的局部最优解在这种情况下不会给你一个全局最优解。
然而，这个问题是一个NP类问题，不能用动态规划来解决。您需要研究一种暴力方法，这将花费指数级的时间。请看下面的树，其中我们从大小1开始。显然，我们没有看到任何逻辑上的重叠子问题，我们可以将其概括为动态编程方法。
https://stackoverflow.com/questions/34755008
复制相似问题
腾讯云开发者
