时间戳

首页 > 解决方案 > 解决单元求和难题的最有效算法是什么？

algorithm - 解决单元求和难题的最有效算法是什么？

问题描述

单元格和拼图定义如下：

给定两组非负整数X = { x 1 , x 2 ,..., x m } 和Y = { y 1 , y 2 ,..., y n }，填充m网格中的每个单元格具有单个非负整数的行和n列，使得x i是每个i ≤ m的第i行中的单元格的总和，并且使得y j是每个j的第j列中的单元格的总和≤ n。

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

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

一个有效的解决方案是：

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

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

标签： algorithm

解决方案

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

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

在你的例子中：

? + ? + ? = 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

推荐阅读