algorithm - 解决细胞总和难题的最有效算法是什么？

Question

单元格和拼图定义如下:

给定两组非负整数 X = {x1, x2,...,xm} 和 是 = {y1, y2,...,yn}，用一个非负整数填充 m 行 n 列的网格中的每个单元格，使得 xi 是每个 i ≤ m 的第 i 行单元格的总和并且 yj 是第 j 列中每个 j ≤ n 的单元格的总和。

例如，如果 X = {7, 13} 和 是 = {8, 9, 3}，那么您的目标是替换以下网格中的问号:

? + ? + ? = 7
+   +   +
? + ? + ? = 13
=   =   =
8   9   3

一个有效的解决方案是:

3 + 1 + 3 = 7
+   +   +
5 + 8 + 0 = 13
=   =   =
8   9   3

对于任意大的 m 和 n，你如何解决这个难题？另外，对于您选择的方法，您是否知道时间复杂度，您能否判断它是否是最有效的算法？

Answer 1

这是一个线性时间算法(O(m + n) 假设我们可以输出一个稀疏矩阵，这是渐近最优的，因为我们必须读取整个输入；否则 O(mn)，这是最优的，因为我们必须写出整个输出)。

用第一行总和和第一列总和的最小值填充左上角的问号。如果第一行总和等于 min，则在该行的其余部分填零。如果第一列总和等于最小值，则在列的其余部分放置零。如果它们仍然存在并递归，则通过从第一行/列中减去新值来提取子问题。

在你的例子中:

? + ? + ? = 7
+   +   +
? + ? + ? = 13
=   =   =
8   9   3

7 和 8 的最小值是 7。

7 + 0 + 0 = 7
+   +   +
? + ? + ? = 13
=   =   =
8   9   3

提取子问题。

? + ? + ? = 13
=   =   =
1   9   3

13 和 1 的最小值为 1。

1 + ? + ? = 13
=   =   =
1   9   3

提取子问题。

? + ? = 12
=   =
9   3

继续下去，直到我们得到最终的解决方案。

7 + 0 + 0 = 7
+   +   +
1 + 9 + 3 = 13
=   =   =
8   9   3