algorithm - 用绝对差替换两个元素并生成数组中的最小可能元素

Question

我有一个大小为 n 的数组，我可以对其应用任意数量的操作(包括零)。在一个操作中，我可以取任意两个元素并将它们替换为两个元素的绝对差。我们必须找到可以使用该操作生成的最小可能元素。 (n<1000)

Here's an example of how operation works. Let the array be [1,3,4]. Applying operation on 1,3 gives [2,4] as the new array.

例如:2 6 11 3 => ans = 0

这是因为 11-6 = 5 且 5-3 = 2 且 2-2 = 0

例如:20 6 4 => ans = 2

例如:2 6 10 14 => ans = 0

例如:2 6 10 => ans = 2

谁能告诉我如何解决这个问题？

编辑:

我们可以使用递归来生成所有可能的情况并从中选择最小的元素。这将具有 O(n^2 !) 的复杂性。

我尝试的另一种方法是对数组进行排序，然后进行递归调用，其中从 0 或 1 开始，我将操作应用于所有连续的元素。这将一直持续到数组中只剩下一个元素，我们可以在递归的任何一点返回最小值。这将具有 O(n^2) 的复杂性，但不一定给出正确答案。

例如:2 6 10 15 => (4 5) & (2 4 15) => (1) & (2 15) & (2 11) => (13) & (9)。最小值将是 1，这就是答案。

Answer 1

当您选择两个元素进行运算时，您就是从较大的元素中减去较小的元素。所以如果你选择 1 和 7，结果是 7 - 1 = 6。

现在有了 2 6 和 8 你可以:

8 - 2 -> 6 然后 6 - 6 = 0

你也可以这样写:8 - 2 - 6 = 0

让我们考虑不同的操作:您可以取两个元素并用它们的和或差来替换它们。

即使使用新操作可以获得完全不同的值，但最接近 0 的元素的绝对值将与使用旧操作完全相同。

首先，让我们尝试使用新操作来解决这个问题，然后我们将确保答案确实与使用旧操作相同。

您要做的是选择初始数组的两个不相交子集，然后从第一个集合中所有元素的总和中减去第二个集合中所有元素的总和。你想找到两个结果最接近 0 的子集。这是一个 NP 问题，可以使用类似于 O(n * 所有元素的总和) 中的背包问题的伪多项式算法有效地解决它

初始数组的每个元素可以属于正集(设置要减去的和)、负集(设置要减去的和)或都不属于它们。换句话说:您可以将每个元素添加到结果中，从结果中减去或保持不变。假设我们已经使用从第一个元素到第 i 个元素计算了所有可获得的值。现在我们考虑第 i+1 个元素。我们可以采用任何可获得的值，并将其增加或减少第 i+1 个元素的值。在对所有元素执行此操作后，我们获得了可从该数组获得的所有可能值。然后我们选择最接近 0 的一个。

现在是更难的部分，为什么它总是正确答案？ 让我们考虑从中获得最小结果的正集和负集。我们希望使用初始操作来实现它。假设负集中的元素多于正集中的元素(否则交换它们)。

如果我们在正集中只有一个元素而在负集中只有一个元素怎么办？那么它们的差值的绝对值就等于我们对其进行运算得到的值。

如果我们在正集中有一个元素，在负集中有两个元素怎么办？

1) 其中一个负元素小于正元素 - 然后我们只需要它们并对它们使用操作。它的结果是正集中的一个新元素。然后我们有之前的案例。

2) 两个负元素都小于正元素。然后，如果我们从否定集中删除更大的元素，我们得到的结果更接近 0，所以这种情况不可能发生。

假设我们在正集中有 n 个元素，在负集中有 m 个元素 (n <= m) 并且我们能够通过使用一些操作来获得它们的和(我们称之为 x)之差的绝对值.现在让我们向负集添加一个元素。如果添加新元素之前的差异是负数，将它减少任何其他数字会使它变小，即离 0 更远，所以这是不可能的。所以差异一定是正的。然后我们可以使用我们对 x 和新元素的操作来获得结果。

现在第二种情况:假设我们在正集中有 n 个元素，在负集中有 m 个元素 (n < m) 并且我们能够获得它们和的差的绝对值(我们再次称它为 x)通过使用一些操作。现在我们向正集添加新元素。同样，差异一定是负数，所以 x 在负数集中。然后对x和新元素进行运算得到结果。

使用归纳我们可以证明答案总是正确的。