将整数分桶到零和桶中的算法

Question

假设我们有一个整数数组(负数和正数)A[1 ... n]这样所有元素的总和为零。现在，每当我有一堆总和为零的整数时，我会将它们称为一个组，我想拆分 A在尽可能多的不相交的群体中。你能推荐任何讨论这个相同问题的论文吗？

Answer 1

听起来您的问题由两个 NP 完全问题组成。

首先是找到解决子集总和问题的所有子集。这个问题确实具有指数时间复杂度(正如评论中的 amit 所暗示的那样)，但从理论的角度来看，它是子集和问题的一个非常合理的扩展。例如，如果您可以通过动态规划解决子集和问题并生成规范的二维数组作为结果，该数组将包含足够的信息以使用回溯生成所有可能的解决方案。

问题中嵌入的第二个 NP 完全问题是整数线性规划问题。给定求解子集求和问题的所有可能子集，总N，我们要选择select 0<=n<=N，使得n的值最大化，A的元素不重复。

我怀疑是否有专门描述此问题的出版物，因为它似乎涉及对已知理论的直接应用。