algorithm - 将 n 个元素分成 k 个组，这些组的总和必须相同

Question

我需要将 n 个元素划分为 k 个组，并且这些组的总和都相同。

例如：

我有一个从 1 到 99 [1, 2, 3, 4, 5...] 的数字列表，我需要将列表分成 3 组。每个组的所有元素之和必须相等。在本例中，n=99 且 k=3。

什么是实现这一目标的有效而优雅的算法？我只是要求使用算法建议；我不想要解决方案。

标签： algorithmlistnumberscomputer-science

Answer 1

让我首先澄清一些事情：当你说你想要一个算法，但没有解决方案时，我必须假设你的意思是你想要一个算法，它会给你一个解决方案k=3和n任何正整数。

我相信这个问题对于 any 有一个解决方案n >= 5，前提是要么n被n+13 整除，要么被 3 整除。

这是因为和1 + ... + n等于n*(n+1)/2，它可以被 3 整除当且仅当其中一个n或n+1可以被 3 整除。

假设n满足这些条件，算法是这样的。

让s = [n*(n+1)/2]/3.

找到m递减序列中的数字，n, n-1, n-2, ...,使得

n + (n - 1) + (n - 2) + ... + m  <=  s  <  n + (n - 1) + (n - 2 ) + ... + m + (m - 1).

让h = s - [n + (n - 1) + (n - 2) + ... + m].

然后h + [n + (n - 1) + (n - 2) + ... + m] = s，我们得到了第一个总和。

请注意，鉴于 m 是如何获得的，h它保证是递减序列，m-2, m-3, ..., 1,因此可用于我们的第一个总和。

我们现在在递减序列中找到数字 q，m-1, m-2, ..., h+1, h, h-1, ..., 1,使得

m + (m - 1) + (m - 2) + ... + q  <=  s  <  m + (m - 1) + (m - 2) + ... + q + (q - 1),

请记住，这些总和可能包括h+1or h-1，但不 h包括。 我在这里滥用总和的符号约定。

这是事情变得有点棘手的地方。

我推测该数字p = s - [m + (m - 1) + (m - 2) + ... + q]是原始序列中剩余（未使用）的数字之一，但我不会证明这一点。（正如他们所说，为读者练习。）

然后p + [m + (m - 1) + (m - 2) + ... + q] = s,，我们有了第二个总和。

（同样：这个数字h可能不在总和中[m + (m - 1) + (m - 2) + ... + q]。）

最后一个总和是所有剩余数字的总和，从原始序列中剩余。

例如（嗯，是的，这是一个解决方案 --- 但仅用于说明目的......）：

1 + ... + 99 = 99*100/2 = 3*550
             = (99 + 98 + 97 + 96 + 95 + 65)
             + (94 + 93 + 92 + 91 + 90 + 89 + 1)
             + (88 + ... + 66 + 64 + ... + 2).

这里n = 99, m = 95, h = 65, q = 89, 和p = 1.