算法 - 最小的减法

Question

我们给出了整数的列表/数组(我们可以使用两者)
在一次移动中我们能够减去其中的两个并放入列表/数组
我们可以做的最低数字(或相同的数字)(> 0)这个操作

我们有6 4 2
第一步采取6和4,我们得到2和2,所以anwser是2

1 7 5
拿7和5,得到2和1,然后得到1

8 20 4 15
拿20和15,我们得到8 5 4,取8和5,得到4和3然后得到1

我可以在时间T(n)= n ^ n中做到这一点,通过比较所有内容或排序每一个回合,我们如何更快地做到这一点？

Answer 1

在研究过类似问题后，我确信没有任何贪心算法可以保证最佳结果。然而，可能没有必要在每一步中都查看两个数字的每一个组合。

看几个例子，很明显，您使用的第一个数字应该始终是最大的数字。对于 3 或 4 个元素的列表，减去第二大的数字始终是最佳选择。然而，对于 5 个或更多元素的列表，似乎没有通用规则。

10,4,3,2,1  ->  6,3,2,1  ->  3,2,1  ->  1,1  ->  1  (largest minus 2nd-largest: 10-6=4)
10,4,3,2,1  ->  9,4,3,2  ->  5,3,2  ->  2,2  ->  2  (largest minus smallest: 10-1=9)

 9,8,7,6,5  ->  1,7,6,5  ->  1,1,5  ->  1,4  ->  3  (largest minus 2nd-largest: 9-8=1)
 9,8,7,6,5  ->  4,8,7,6  ->  4,1,6  ->  2,1  ->  1  (largest minus smallest: 9-5=4)

我测试了一种算法，该算法在每个步骤中尝试最小和第二大的数字（导致 2 ⁿ次递归），但发现了一个不起作用的示例：99,78,68,56,52,4,3。

仅使用最小或第二大找到的最佳解决方案是 6：

99 78 68 56 52  4  3
96 78 68 56 52  4
92 78 68 56 52
40 78 68 56
40 10    56
   10    16
          6

通过暴力破解所有选项找到的最佳解决方案是 1：

99 78 68 56 52  4  3
31 78    56 52  4  3
31 26    56     4  3
   26    25     4  3
    1           4  3
    1           1

如果您使用最大的数字作为唯一的优化，这将导致以下算法：

• 找出最大的数
• 遍历所有其他数字，从最大数字中减去它，然后递归

这比尝试两个数字的每种组合或在每个步骤后进行排序的时间复杂度更低。