将值均匀分配到容器中的算法？

Question

有没有人知道将数字均匀分配到一定数量的容器中的方法,确保容器的总值尽可能均匀？

编辑:"尽可能",我的意思是如果按X容器分配,每个容器的总数将接近总平均值.

现在我只是对数字数组进行排序(降序),然后将它们的值无关地分配到容器中.分配到三个容器中的一组1000,200,20,1000等于[2000],[200],[20].

我想做的是:

Example

Set of numbers: 10 30 503 23 1 85 355
If I were to distribute these into three containers I would just pick the highest first and then distribute them as I go, like this:
Cont 1 = 503
Cont 2 = 355
Cont 3 = 85 + 30 + 23 + 10 + 1

This will give the best possible distribution that you can get with the values provided.

但我不知道在代码中表达这一点的简洁方法.

想法？

Answer 1

您是否有一个大型数据集，对象大小差异很大，并且要求您必须找到最佳解决方案？如果是这样，这是不现实的。

但好消息是，许多理论上 NP 完全的问题在现实世界中很容易！如果您的数据点数量相对较小，那么您可能可以进行智能（但仍然彻底）搜索并找到全局最佳解决方案。

此外，如果您有一个表现良好的数据集，值的方差非常小，那么您可能很快就会偶然发现一个完全均匀地填充所有容器的解决方案。如果是这样，那么这显然是最好的答案。即使在非常大的数据集上，这也能很好地工作。（我认为您在这里想要的是一个包含许多小值的数据集，可以用来在最后轻松地整理事情。）。

所以，不要放弃！首先，对数据进行排序并从最大到最小考虑数据点。在每个阶段，将下一个值分配给当前最小的容器。这可能不会在所有情况下为您提供最佳解决方案，但在实践中可能相当合理。

排序一下1000, 200, 20, 1000，就给你了1000, 1000, 200, 20。该算法将为您提供：

1000        = 1000
1000        = 1000
200   +20   =  220

这恰好是最佳解决方案，但情况并不总是如此。

====

如果您愿意并且能够尝试更复杂的算法，请查找分区问题：

尽管划分问题是 NP 完全问题，但存在伪多项式时间动态规划解决方案，并且存在可以在许多情况下以最优或近似方式解决该问题的启发式方法。因此，它被称为“最简单的难题”。

划分问题有一个优化版本，即将多重集 S 划分为两个子集 S1、S2，使得 S1 中的元素之和与 S2 中的元素之和之间的差异最小化。