algorithm - 从随机数序列中选择大小相等的数字组

Question

假设我有一个 100 个数字的列表，我想将它们分成 5 个组，每个组中的总和最接近数字的平均值。

最简单的解决方案是对一百个数字进行排序并取最大数字并继续添加最小数字，直到总和超过平均值。

显然这不会带来最好的结果。我想我们可以使用 BFS 或 DFS 或其他一些搜索算法。喜欢 A* 以获得最佳结果。

有没有人有一个简单的解决方案？伪代码已经足够好了。谢谢！

Answer 1

这听起来像是背包问题的一种变体，如果我对您的解释正确，则可能是多背包问题。你不能想出一个简单的问题吗？:)

Answer 2

可以使用的有效算法（解决方案）是箱包装算法的最佳拟合的变体。但是，我们必须应用一种变体，其中我们有 5 个我们想要的不同的数字组，而不是寻找使用最少数量的组。

该算法首先找到所有 100 个数字列表的平均值。该平均值将用作我们尝试将数字放入的所有 5 个组（箱）的最大容量。然后，我们在 100 个数字列表中找到不超过我们组最大容量的最大数字，并将其分配给我们的第一个组。（我们可以在 log(n) 时间内找到它，因为我们可以使用自平衡二叉搜索树）。我们跟踪我们当前组的填充情况。然后，我们找到适合我们当前组的下一个最大数字，直到我们达到最大容量或没有其他数字可以让该组达到最大容量。在这两种情况中的任何一种情况下，我们都会进入下一组并使用我们的数字列表中留下的数字重复我们的算法。一旦我们从一个组继续前进，我们还必须跟踪该组的当前总和。我们继续，直到我们达到所有 5 组的最高容量。如果还有任何数字，我们将它们放在总和最低的组中（因为我们一直在跟踪这些总和）。由于装箱的性质，这实际上是一个运行时间为 Θ(nlogn) 的贪心算法。