8

免责声明：这不是任何作业，当我浏览所有圣诞贺卡时，我才想到这个问题

问题如下：我们有 M 个信封和 N 个字母，每个字母被描述为一对正整数。信封和信件都是矩形的，显然可以旋转。如果两个尺寸都小于或等于信封的尺寸，则一封信可以装入信封。目标是找到最大的信封字母匹配。

该问题很容易转换为最大二分匹配问题，其中O(sqrt(M+N) * MN)存在运行算法（Hopcroft-Karp，转换运行微不足道O(MN)）。我试图提出一个贪心算法或动态方法，但我没有找到任何方法。

你知道任何更快的解决方案吗？

4

3 回答 3

0

以下“贪婪”型方法可能会有所帮助。

将 m[i] 定义为包络 i 的两个整数中的最小值。

mins = distinct values of m[i], in increasing order
letters_to_match = all letters
for min in mins:
    envs = envelopes i with m[i] == min
    match letters_to_match with envs
    remove matched letters from letters_to_match
于 2014-01-06T10:49:30.800 回答
0

这不等于最大二分匹配吗？

即假设你有一个解决这个问题的算法，那么你可以解决最大二分匹配。

给定一个二分图，我们可以将信封和字母（即两个正整数）分配给每个节点......

于 2014-04-02T04:03:31.443 回答
0

这可以O(max(M,N) log(max(M,N)))通过 2D 垂直扫描线算法在（排序字母和信封的时间）中解决。这与O(M+N log (M+N)).

  1. 由于允许旋转，因此交换任意一(x, y)对字母/信封尺寸，以便x <= y.

  2. 合并列表，标记每个点的原始列表。例如，我们可以通过使(x, y, 'E')信封列表中的表示点和字母的“L”来做到这一点。

  3. 将列表按 排序x，然后按ytiebreak 排序，如果仍然并列，则在 'E' 之前使用 'L'。我们将把一个字母(x0, y0, 'L')视为 2D 空间中的一个点，(x1, y1, 'E')当且仅当 时，它可以匹配任何“信封”点x0 <= y0 and x1 <= y1。

  4. 初始化一个平衡二叉搜索树 (BST) unmatched_letters，它将包含我们迄今为止不匹配的字母，它们在 BST 中的键/排序仅基于它们的 y 值。

这个想法是我们将在点上移动一条垂直扫描线，从左到右，从下到上处理线上的点（这是我们的列表已经排序的确切顺序）：

  • 如果我们看到一个字母，我们会将它添加到我们的unmatched_lettersBST，按“y”排序。这意味着我们在添加后看到的任何信封只需要检查更大/相等的“y”值（扫描线确保后面的 x 值不会更小）。
  • 如果我们看到一个信封，我们将尝试使用二进制搜索将其与 BST 中可用的最高字母匹配。如果没有，我们可以“扔掉”/忽略那个信封，因为我们将来看到的任何字母都将具有比这个信封更高的 x 或 y 值。否则，匹配它们。您可以通过贪婪交换参数证明这将给出最佳解决方案；如果它不是太长或不重要，我可能会包括一个证明。

对于我们刚刚描述的步骤的更详细的“伪代码”版本：

  1. 遍历(x0, y0, category)我们列表中的点。如果category == 'L'，将其插入到unmatched_letterswith key y0。如果category == 'E'，则对其中最大的键值进行二分搜索，最多unmatched_letters为y0。如果匹配：该字母在x0之前处理后最多有一个 x 值。删除那封信，并将其作为我们解决方案的一部分与此信封一起记录。

由于我们所做的只是对列表进行排序和迭代，这显然可以在O(sorting). 不难争论为什么这必须给出最大匹配，但是贪婪算法正确性的确切证明可能很长。部分论点是这样的：如果我们与任何固定的最优解进行比较，并且最早的区别（通过 x 坐标）是贪心匹配信封“E1”与字母“L1”而最优不匹配，那么有两种（不相交的）可能性：

  • 在最优解中，“E1”匹配不同的字母“L2”。通过构造，“L2”的 y 值最多与“L1”一样大，因此如果“L1”与最优解中的后一个（按 x 值）包络匹配，则该后一个包络也必须适合“L2” ' （如果不是，我们可以交换 'L1' 和 'L2' 以优化匹配贪婪）。
  • 在最优解中，“L1”匹配不同的包络“E2”。然后，再一次，最优解中的信封“E1”与一个较小或相等的 y 值字母（或空）匹配，我们可以在最优解中交换这些配对以匹配贪婪。
于 2022-02-19T00:29:44.123 回答