将自然数分配到相等桩的算法

Question

我正在寻找一种可以采用一组自然数的算法，例如：

S = {1, 3, 4, 2, 9, 34, 432, 43}

然后将它们分成尽可能相等的桩。桩的数量预定义为n。

目标是使每个桩和最低桩之间的差异总和最小。

这是一个例子。

假设你有：

S = { 1, 2, 2, 3, 1, 2, 3 }
n = 3

然后解决方案可能是

N1 = { 1, 2 }
N2 = { 2, 3 }
N3 = { 1, 2, 3 }

这些桩的总和将是3,5和6.误差将是：（5 - 3）+（6 - 3）= 5。

该算法需要找到具有最低误差的解决方案。

任何帮助表示赞赏。如果不清楚，请评论。

Answer 1

我认为没有有效的方法来解决这个问题，因为它是一个NP难问题。

证明：

我们将你提出的问题表示为P *，

我们可以通过以下方式将分区问题（已知的NP-hard）减少为P *给定任意分区问题P1，我们要求解决P *的黑盒解决P1 = N = 2（即，将该组划分为2最小化不同的桩）。

如果黑盒子返回的差值为零，则 - >有一个P1的解决方案

如果黑盒子返回的差异非零， - >没有P1的解决方案

因此，P *是NP难的

Answer 2

这听起来像是https://en.m.wikipedia.org/wiki/Bin_packing_problem的变种。然而，没有给出箱的尺寸，因此它至少与箱包装一样坚硬。因此问题是NP难。

对于近似解决方案，您可以例如计算平均箱尺寸并执行首次拟合或最佳拟合的适应以允许小的过度包装。