3

给定 n 对数字，第一个数字总是小于第二个数字。当且仅当 b <= c 时，一对 (c, d) 可以跟随一对 (a, b)。可以以这种方式形成对链。找出可以由一组给定的对组成的最长链。

例如{ (1,2), (3,4), (5,7), (9,10), (7,9), (8,9), (0,6) }

所以输出应该是：{(1,2), (3,4), (5,7), (8,9), (9,10)}

我的算法如下：

 1. Sort the list according to the 2nd number of elements
i.e.`{ (1,2), (3,4), (0,6), (5,7), (7,9), (8,9), (9,10)  }`
 2. choose the first element from the list  i.e. `(1,2)`
 3. for each element e in the list left
      4. choose this element e if the first number of the element is greater than the 2nd number of the previous element. i.e. after `(1,2)` choose `(3,4)` because `3 > 2.`

在上述算法之后，您将获得输出为{(1,2), (3,4), (5,7), (8,9), (9,10)}.

请让我知道算法的正确性。谢谢。

编辑：

更直观的正确性证明：

证明：在链中包含更多对的唯一方法是将一对替换为 Y 值较小的一对，以允许下一对具有较小的 X 值，从而可能适合之前无法适合的另一对。如果您将一对替换为具有相同 Y 值的一对，您将一无所获。如果替换具有较大的 Y 值，那么您所做的只是可能阻止一些以前适合的对。

因为这些对已按 Y 值排序，所以您永远不会找到具有较小 Y 的替代品。在排序的对中“向前”看，它们都将具有相同或更大的 Y 值。“向后看”，最初从链中淘汰的任何东西都是因为 X 值不够高，情况仍然如此。

这是取自这里

4

3 回答 3

2

它是正确的。这是一个证明：

让s1, s2, ..., sl成为您的算法找到的对，并i1, i2, ..., ik成为最佳解决方案。

我们有：

l == k => your algorithm is obviously correct, since it's clear that
          it doesn't produce invalid solutions;

l > k => this would contradict our hypothesis that i1, ..., ik is optimal,
         so it makes no sense to bother with this;

l < k => this would mean that your algorithm is wrong. 
         Let's assume this is the case.

假设i1 != s1。在这种情况下，我们可以在最优解中替换为 ，因为i1是完成时间最短的对。所以仍然是一个最佳解决方案。s1s1s1, i2, ..., ik

让t <= l成为 的第一个索引st != it。因此，s1, s2, ..., s[t-1], it, ...是一个最优解。我们可以替换it为，st因为：

  • st不是t-1最优解的第一个元素的一部分；
  • st不属于i[t+1], ..., ik. 如果是，那将意味着完成st后开始it，这将与算法选择的方式相矛盾st。

因此，以这种方式继续下去，我们的最佳解决方案是s1, s2, ..., sl, ..., ik。这意味着可以在 之后添加更多对sl，但这与算法的工作方式相矛盾，所以我们有l = k，并且算法是正确的。

于 2013-08-02T14:37:27.817 回答
2
  1. 对(c, d)可以跟随一对(a, b)当且仅当b <= c
  2. 对(c, d)有约束d > c

因此我们可以说

b <= c

变成

b < d because d > c

因此最长的序列将从最小的第二个元素开始。因此，您根据第二个元素对它们进行排序选择第一个元素并根据您的原始条件进行比较b <= c

算法是正确的。当您获得第一个元素（贪婪）时，您将保持原始约束不变，即b <= c.

注意：您不能使用b < d条件来比较排序后的元素，因为您无法从中推断b <= c（原始条件），b < d但其他方式是可能的。

于 2013-08-02T14:42:15.013 回答
-1

这个问题可以用很多方法来解决 相同类型的问题已经存在 检查它给你 n 对数字。在每一对中，第一个数字总是小于第二个数字。如果 b < c，一对 (c, d) 可以跟随另一对 (a, b)。可以以这种方式形成对链。找出可以由一组给定的对组成的最长链。

你可以去这里，那里有很多有用的资源

最大长度链对

最长递增序列

于 2013-08-02T14:19:10.350 回答