nx3 数组中的最小数字总和，以便在那里表示每一列和每一行

Question

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

• 我们只从每一行中选择一个元素，
• 每一行都必须表示，所以在这样的总和中每一行必须恰好有一个数字，
• 每一列都必须表示，因此必须至少有一个数字位于第 1 列，至少有一个位于第 2 列，至少有一个位于第 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 所以那种贪心的方法被证明是不成功的。有人能建议我应该改变我的方法吗？

Answer 1

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

1. 选取的元素涵盖所有 3 列。我们完成了。
2. 选取的元素包括2列：
   • 再次遍历所有行并考虑缺失行中的元素与选取的元素之间的差异。
   • 找到差异最小的行并切换该行中的选项。我们完了。 （这是 O(n)。）
3. 选取的元素只包含1列：
   • 再次遍历所有行并考虑第一个缺失行中的元素与选取的元素之间的差异，以及第二个缺失行中的元素与选取的元素之间的差异。
   • 找到第一个缺失行中的元素与选取的元素之间差异最小和第二小的 2 行。
   • 找到第二个缺失行中的元素与选取的元素之间差异最小和次小的 2 行。
   • 现在你只需要考虑切换的四种可能性，选择一个更好的（并且满足约束条件）。我们完了。 （这是在 O(n) 中完成的。）