将任意数据数组分组为N个bin

Question

我想将任意大小的随机值数组n分组,以便任何一个组/ bin中的值之和尽可能相等.

因此,对于价值观[1, 2, 4, 5]和n = 2,输出桶水就[sum(5+1), sum(4+2)].

我遇到的一些可能性:

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

似乎最优解(在给定输入数组的情况下,二进制位的内容之和尽可能相等)可能是非平凡的; 所以目前我倾向于最后一个选项,但感觉我可能错过了更优雅的解决方案？

Answer 1

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

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

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

步骤 1. 计算每个 bin 的预期总和。让A成为你的数组，那么每个 bin 的预期总和是SumBin = SUM(A) / n （你的数组中所有元素的总和超过 bin 的数量）。

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

步骤 3.将袋子分成n 个组（最好是随机的，这样每个元素以概率 1/ n结束在某个 bin i 中）。此时，您的 bin 已包含所有元素，而The Bag是空的。

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

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

步骤 6. 转到步骤 3。

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

如果您对上述随机算法持怀疑态度，则在第一次迭代后返回第 3 步，而不是随机分配元素，您可以通过运行匈牙利算法以最佳方式执行此操作，但我不确定这会保证更好总体结果。