algorithm - 划分整数集

Question

我遇到了算法问题的解决方案，如下所述。

我们有一组整数(例如数组)。我们的任务是将它们分成总和彼此相等的组(它们不必具有相同数量的元素)。如果原始集不能被划分，我们必须给出“不可能划分”的答案。

例如:集合 A 被赋予 [-7 3 3 1 2 5 14]。答案是[-7 14], [3 3 1], [2 5]。

似乎很容易说什么时候肯定是不可能的。当原始集的总和不能被 3 整除时:sum(A) % 3 != 0。

你知道如何解决这个问题吗？

Answer 1

这是 3-partition problem partition problem 的变体，不同之处在于经典的划分问题将集合分成两组(而不是三组)，它们的总和彼此相等。这个问题是 NP 完全问题，因此您几乎可以肯定不会为它找到多项式时间解决方案； 2-划分问题有一个伪多项式时间解，但3-划分问题没有。

参见 this answer有关如何将 2 分区算法调整为 3 分区算法的概述。另见 this paper并行解决方案。