我想将任意大小的随机值数组分组为n个组,这样任何一个组/ bin中的值之和尽可能相等.
因此,对于值[1,2,4,5]和n = 2,输出桶应为[sum(5 1),sum(4 2)].
我遇到的一些可能性：
>完全详尽的广泛搜索
>具有硬编码的停止条件的随机过程
>从排序数组的一端开始,分组直到总和等于全局平均值,然后移动到下一个组,直到达到n
似乎最优解(在给定输入数组的情况下,二进制位的内容之和尽可能相等)可能是非平凡的;所以目前我倾向于最后一个选项,但感觉我可能错过了更优雅的解决方案？
如果您的数据集足够小,可以使用强力算法(探索所有组合).
但是,如果您的数据集很大,那么您需要一个多项式时间算法,它不能为您提供最佳解决方案,但需要很好的近似.在这种情况下,我建议你使用类似于K-Means的东西……
步骤1.计算每个箱的预期总和.设A是你的数组,然后每个bin的预期总和是SumBin = SUM(A)/ n(数组中所有元素与二进制数之和的总和).
第2步.将数组的所有元素放在一些我们称之为The Bag的集合(例如另一个数组)中(这只是一个概念,所以你理解了下一步).
步骤3.将Bag分成n组(最好是随机的,这样每个元素最终以某个bin i结束,概率为1 / n).此时,你的垃圾桶里有所有的元素,而且这个垃圾袋是空的.
步骤4.计算每个bin的总和.如果结果与上次迭代相同,则退出. (这是K-Means的预期步骤)
步骤5.对于每个bin i,如果其总和大于SumBin,则选择大于SumBin的第一个元素并将其放回The Bag中;如果它的总和小于SumBin,选择少于SumBin的第一个元素并放回The Bag中.这是K-Means的梯度下降步骤(又称最大化步骤).
步骤6.转到步骤3.
这个算法只是一个近似值,但它很快并且保证收敛.
如果你对如上所述的随机算法持怀疑态度,在第一次迭代后回到第3步,而不是随机分配元素,你可以通过运行Hungarian algorithm来做到最佳,但我不确定这会更好地保证 – 所有结果.