algorithm - 如何证明数学中的编程功能

Question

这是一道编程题:

给出了四个整数 A、B、C 和 D。它们的混合是由这四个整数按某种顺序组成的任何零索引数组 M。如果给定的所有整数都是唯一的，则它们有 24 种不同的组合。

给定整数的最佳组合是它们的任意组合 M 使得值: F(M) = abs(M[0]-M[1]) + abs(M[1]-M[2]) + abs(M[2]-M[3]) 是最大的。

写一个函数:

class Solution { int solution(int A, int B, int C, int D); }

给定四个整数 A、B、C 和 D，找到它们的最佳组合 M 并返回 F(M) 的值。

例如，考虑以下整数: A = 5 B = 3 C = -1 D = 5

它们的最佳组合如下:

M[0] = 5

M[1] = -1

M[2] = 5

M[3] = 3

结果是 F(M) = 14。

假设:

A、B、C 和 D 是 [−1,000,000..1,000,000] 范围内的整数。

复杂度:

预期的最坏情况时间复杂度为 O(1)；预期的最坏情况空间复杂度为 O(1)。

我的想法是:

1. 创建一个数组 N 并按后代顺序对数字进行排序
2. 赋值 M0[0] = N[3], M[1] = N[0], M[2] = N[2], M[3] = V[1]
3. 周四，Abs[最大数 - 最小数] + [最小数 - 第二大数] + [第二大数 - 第二小数]

如何证明我的想法是正确的？如何用数学方式证明？

Answer 1

因为似乎没有要求您提供通用解决方案并且问题规模很小，所以最直接的方法是将调用中的 24 种排列硬编码到一个评估成本并保持最佳状态的函数中:

F(A, B, C, D); 
F(A, B, D, C); 
F(A, C, B, D);
...

作为一个小的优化，您可以删除一半的案例，它们是对称的(函数以相同的方式从左到右或从右到左求值)，因此只需要 12 次调用。

---

进阶说明:

我从维基百科上找到了这句话:“在具有非负边权重的加权完全图中，加权最长路径问题与旅行商路径问题相同，因为最长路径总是包含所有顶点。”

如果我是对的，我们正是在这种情况下，所以问题是 NP-hard。这意味着没有希望找到比穷举搜索更好的方法，如上所述。 (无论如何，这个问题的实例享有三角不等式，这可能会使它更容易......)