0

这是我连续第三天要解决的算法问题的一部分。所以我们得到了一个 3xn（n 行，3 列）的数组。我们需要找到这样的最小总和：

  • 我们只从每一行中选择一个元素，
  • 必须表示每一行，因此在这样的总和中，每一行必须有一个数字，
  • 每列必须表示，因此必须至少有一个数字位于第一列，至少一个位于第二列，至少一个位于第三列。

让我们以该数组来说明问题：

6 2 4
8 7 5
6 2 4
9 6 5

在这种情况下，最小的总和是8 (1st column, 2nd row) + 2 (2nd column, 1st row) + 5 (3rd column,4th row) + 2 (2nd column,3rd row) = 17

我尝试以如此贪婪的方式解决这个问题，我创建了该数组的三个副本，按各自的列对它们中的每一个进行排序，然后尝试3!使三个数字的总和最小，并为其余数字加上最小值，但随后上述情况的解决方案是：

6 (1st column, 3rd row) + 2 (2nd column, 1st row) + 5 (3rd column, 4th row) + remaining 5 (3rd column, 2nd row) = 18所以这种贪婪的方法被证明是不成功的。有人会建议我应该改变我的方法以使其成为可行的方法吗？

4

1 回答 1

0

循环遍历所有行，并在每一行中选择该行的最小元素。（这是 O(n)。）现在有 3 种可能性：

  1. 选取的元素覆盖所有 3 列。我们完了。
  2. 选取的元素涵盖 2 列：
    • 再次遍历所有行，并考虑缺失行中的元素与选取的元素之间的差异。
    • 找到差异最小的行并在该行中切换选项。我们完了。（这是 O(n)。）
  3. 选取的元素仅覆盖 1 列：
    • 再次遍历所有行并考虑第一个缺失行中的元素与拾取元素之间的差异，以及第二个缺失行中的元素与拾取元素之间的差异。
    • 查找第一个缺失行中的元素与选取的元素之间差异最小和第二小的 2 行。
    • 查找第二个缺失行中的元素与选取的元素之间差异最小和次小的 2 行。
    • 现在您只需要考虑切换的四种可能性并选择哪一种更好（并满足约束条件）。我们完了。（这是在 O(n) 中完成的。）
于 2020-11-19T17:01:23.980 回答