algorithm - 从数字的差异中获得尽可能低的总和

Question

我必须从数字的差异中找到可能的最低总和。

假设我有 4 个数字。 1515、1520、1500 和 1535。最小的差和是 30，因为 1535 - 1520 = 15 && 1515 - 1500 = 15 和 15 + 15 = 30。如果我这样做:1520 - 1515 = 5 && 1535 - 1500 = 35 加起来就是 40。

希望你明白了，如果没有，问我。

有什么关于如何编程的想法吗？我刚在网上找到这个，试图将我的语言翻译成英语。听起来很有趣。我不能做蛮力，因为编译需要很长时间。我不需要代码，只需要如何编程的想法或一小段代码。

谢谢。

编辑: 我没有发布所有内容……再发布一版:

我假设有 8 个可能的数字。但是我只需要取其中的 6 个就可以得出最小的和。例如，数字 1731, 1572, 2041, 1561, 1682, 1572, 1609, 1731，最小和为 48，但这里我只需要从 8 中取 6 个数字。

Answer 1

考虑到编辑:

首先对列表进行排序。然后使用动态规划解决方案，状态 i，n 表示仅考虑第一个 i< 时 n 差异的最小总和/em> 序列中的数字。初始状态:dp[*][0] = 0，其他一切 = 无穷大。使用两个循环:外循环通过 i 从 1 循环到 N，内循环通过 n 从 0 循环到 R(在您的示例中为 3在您的编辑中 - 这使用 3 对数字，这意味着 6 个单独的数字)。你的循环关系是 dp[i][n] = min(dp[i-1][n], dp[i-2][n-1] + seq[i] - seq[i-1]).

您必须注意处理我忽略的边界情况，但总体思路应该可行，并将在 O(N log N + NR) 并使用 O(NR) 空间。