java - 寻找可用于一组数字排列的最小增量

Question

假设我们有一组 12 个对象，比如说 {1,2,3,4,5,6,7,8,9,10,11,12}。我们必须把这个集合分成由三个对象组成的4个较小的集合，使这四个集合的最大和和最小和最小。我们必须找到这个区别。在我们的示例中，{1,7,12},(3,8,9},{4,5,10},{2,6,11}。这四个集合满足问题，因为它们的总和为 20 和 19，表示增量为 1，即我们的答案。

对于任意 12 个值，如何解决这个问题？

我已经尝试将所述集合的所有分区枚举为 4 组，每组 3 组，并找到一个具有最佳分数的。然而，时间紧迫，所以我想知道如何在 Java 中解决这个问题

我现在没有确切的代码，但它本质上是 9 个嵌套的 for 循环，其中嵌套的前三个是一组，接下来的三个是下一组，最后三个是另一组，剩下的三个是另一套。我使用了一个二维数组，这样值就会在 score[i][0] 中，而 score[i][1] 会作为一个指示器让我知道 score[i][0] 中的值是否已经被放置成一个集合。

这当然会变得乏味且效率低下。

Answer 1

您可以通过找到总和必须接近的值来实现更好的优化来轻松简化问题:

例如，在您的简单情况下 (1,2...12)，则每项的总和为 78。因此，每个组的总和必须非常接近 78/4=19。

那么，让我们尝试一个非常简单的算法:

- compute TOTAL_SUM = SUM(terms)
- compute TARGET_SUM = TOTAL_SUM / number(terms)
- set DELTA=0
- loop {
-    Try to split terms in groups where TARGET_SUM - DELTA <= SUM <= TARGET_SUM + DELTA
-    if a solution is found, exit
-    DELTA = DELTA + 1
-    }

好吧，我在“尝试拆分...”这一步中并没有帮到你多少。但它应该看起来像您自己的解决方案，只是您有额外的约束可以帮助您加快流程。

希望这对您有所帮助。