如何将一行数字分为 N 组，使得每组的总和最接近其平均值？

Question

我有以下问题：我有 M 个数字排列成一行。我需要将线分为 N 组，以便每组的数字总和最接近这些总和的平均值（按某种度量标准）。实际的度量并不重要：我们可以选择最小化绝对差的总和或方差等，具体取决于哪个会导致最简单的解决方案。

类似的问题是集合的划分，这是 NP Hard 问题。然而，这里我们有额外的约束：组必须打包连续的数字，因此可能有一个不涉及暴力搜索的解决方案。数字很​​大。

编辑

例子：

数字：1 2 3 4 5 6 7 8 9 10，需要分为3组

假设我们想要最小化绝对差之和 (SAD)。

组数：(1) 1 2 3 4 5 6（总和 = 21）；(2) 7 8（总和 = 15）；(3) 9 10（总和 = 19）

Mean = (21+15+19)/3 = 18.33, SAD = 21-18.33 + 18.33-15 + 19-18.33 = 6.67 <- 这就是我们想要最小化的值。

Answer 1

一旦您知道总和应该是多少，您就可以创建接近该总和的组。如果您的指标很好，那么您应该能够使用二分搜索来查找实际总和。当您的目标是特定总和时，您可以浏览列表，将数字添加到组中，直到组总和超过总和大小。然后要么取或不取最后一个整数。执行此操作遍历整个列表，看看哪些组的总和与总和偏差最大。然后返回列表，尝试落在偏差范围内的组大小的组合......它应该足够快。否则使用动态规划。