python - 将任意数据数组分组到 N 个 bin 中

Question

我想将一个任意大小的随机值数组分组到 n 组中，这样任何一组/bin 中的值的总和尽可能相等。

因此对于值 [1, 2, 4, 5] 和 n = 2，输出桶应该是 [sum(5+1),总和(4 + 2)] 。

我想到的一些可能性:

• 完全详尽的广度优先搜索
• 停止条件硬编码的随机过程
• 从排好序的数组的一端开始分组，直到总和等于全局平均值，然后移动到下一组，直到达到n

似乎最佳解决方案(在给定输入数组的情况下，箱子内容的总和尽可能相等)可能并不平凡；所以目前我倾向于最后一个选项，但感觉我可能缺少更优雅的解决方案？

Answer 1

这是一个 NP-hard 问题。换句话说，如果不探索所有组合就不可能找到最佳解决方案，并且组合的数量是 n^M(其中 M 是数组的大小，n 是 bean 的数量)。这是一个与 clustering 非常相似的问题，这也是 NP 难的。

如果您的数据集小到足以处理，则最好使用强力算法(探索所有组合)。

但是，如果您的数据集很大，您将需要一个多项式时间算法，它不会为您提供最佳解决方案，而是一个很好的近似值。在这种情况下，我建议您使用类似于 K-Means 的东西...

第 1 步。计算每个 bin 的预期总和。设 A 为您的数组，则每个 bin 的预期总和为 SumBin = SUM(A)/n(数组中所有元素的总和超过 bin 的数量) .

第 2 步。将数组的所有元素放入我们称为 The Bag 的某个集合(例如另一个数组)中(这只是一个概念，因此您可以理解接下来的步骤)。

第 3 步。将 The Bag 分成 n 组(最好是随机分组，以便每个元素以概率 1 结束在某个 bin i 中/n)。此时，您的箱子里有所有的元素，The Bag 是空的。

第 4 步。计算每个 bin 的总和。如果结果与上次迭代相同，则退出。 (这是 K-Means 的期望步骤)

步骤 5. 对于每个 bin i，如果其总和大于 SumBin，则选择第一个大于 SumBin 的元素并将其放入回到The Bag；如果其总和小于 SumBin，则选择第一个小于 SumBin 的元素并放回The Bag。这是 K-Means 的梯度下降步骤(又名最大化步骤)。

第 6 步。转到第 3 步。

这个算法只是一个近似值，但它很快并且保证收敛。

如果您对上述随机算法持怀疑态度，在第一次迭代后返回第 3 步时，您可以通过运行 Hungarian algorithm 来优化分配元素，而不是随机分配元素。 ，但我不确定这会保证更好的整体结果。