将数字分组，以便他们的总和差异最小

我发现了一些相似的线程，但我相信我的是有点独特的。 这将是很难写，所以请忍受我。

我有10个账号，每个账号都有一个不能分割的静态数字。 我有3名员工需要将这些帐户尽可能分开。 他们不能共享一个帐户。

例如：

(A)lpha = 15 (B)eta = 30 (C)harlie = 22 (D)elta = 19 (E)cho = 28 (F)ranklin = 3 (G)roto = 7 (H)enry = 28 (I)ndia = 38 (J)uliet = 48 

总数为238.在完美的世界里，2个人会得到79个，一个人会有80个。但是，请记住，我们不能分开一个帐户，所以我们需要添加帐户，以尽可能接近均匀传播。

我需要一个公式，因为这样的情况经常发生，需要一些时间来解决这个问题。 我相信这将是最好的帮手列执行。

我最接近的是：

 FHJ = 79 ABCG = 74 DEI = 85 

但是，由于这是再次发生，可能发生在更多的帐户，我需要一些我可以重复使用的东西。

Answer 1

另一个不那么复杂但近似的解决scheme是

1. 从最高到最低的数字对您的帐户进行sorting
2. 开始把数字分成3组（A，B，C）
   • 从最高的3个数字开始（ 48|J ， 38|I ， 30|B ）sorting到A，B和C组
   • 下一个最高的数字（ 28|E ）进入总和最低的组（C）
   • 下一个最高的数字（ 28|H ）进入总和最低的组（B）
   • 等等 …

你应该结束这个：

这与您的手动解决scheme不同，但更接近。 如果你看到不同之处：

• 从上面的解决scheme： 81 - 77 = 4
• 您的手动解决scheme： 85 - 74 = 11

这个algorithm是一个近似，它不总是find最好的解决scheme，但是如果最低和最高的数字之间的差别不是太大，那么结果就非常接近最佳解决scheme。

Answer 2

这被称为分区问题 。 您可以尝试从Wikipedia页面实现伪多项式时间algorithm。 你必须修改3个分区而不是2个。

 INPUT: A list of integers S OUTPUT: True if S can be partitioned into two subsets that have equal sum 1 function find_partition(S): 2 n ← |S| 3 K ← sum(S) 4 P ← empty boolean table of size (floor(K/2)+ 1) by (n + 1) 5 initialize top row (P(0,x)) of P to True 6 initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False 7 for i from 1 to floor(K/2) 8 for j from 1 to n 9 if (iS[j-1]) >= 0 10 P(i, j) ← P(i, j-1) or P(iS[j-1], j-1) 11 else 12 P(i, j) ← P(i, j-1) 13 return P(floor(K/2), n)