0

我的规则：

  • 允许重复
  • 显然允许负数
  • 由于我提到了分区，这意味着您不能将数组中的元素放在超过 1 个分区中
    • 分区中的元素是子集/不需要是连续的数组块
    • 输入数组中的元素未按排序顺序
    • 输入数组中所有元素的总和将为 0（给定条件）

示例：如果 A = {-2,-4,-6,+6,+6} 那么 B={{-2,-4,6},{+6,-6}} 是最大 no 的结果分区数

仅供参考，我想返回所有分区而不是分区数。

根据我的研究，这似乎是一个 NP-hard/complete 问题。但我不确定，如果有人能解释最好的解决方法（即使它很慢），我将不胜感激。一些伪代码也会受到赞赏。

谢谢你。

4

2 回答 2

2

这绝对有一种NP难的感觉。特别是是否可以进行 2 个分区与 1 个分区的问题是一个问题，即除最后一个之外的所有元素的适当子集是否加起来是最后一个的负数，这是子集和问题的一个变体。因此，即使通过拆分其中一个分区来验证无法进一步改进答案也可能是 NP 完全的！

但在实践中如何解决这个问题？

第 1 步是生成一个数据结构，表示所有可能的分区，包括总和为 0 的第一个元素。这可以像标准子集总和算法一样解决。有了一个双向链表的想法，我们可以从中获取信息。（双向链表通常与数组的大小乘以找到的不同和的数量成正比，但在解码时，它可能会导致指数级的分区数。

双向链表会让您头晕目眩，因此您可能希望使用如下语法糖：

from collections import namedtuple
Node = namedtuple('Node', ['ind', 'prev'])
Paths = namedtuple('Paths', ['node', 'prev'])

ind数组的索引在哪里，node始终是 a Node，并且prev始终是 a Pathsor None。

现在 aNode说“在以下先前的选择中包含此索引和任何有效路径”。并且 aPaths说“这是一个通向这里的节点，还有一条通往其他方式的先前路径。”

有了这个，我们可以做到以下几点：

# We only want paths that take the 0th index.
ways_to_get_to_n = {elements[0], Paths(Node(0, None), None)}

for i in range(1, len(elements)):
    element = elements[i]
    new_ways_to_get_n = {}
    for value, ways in ways_to_get_n.items():
        new_ways_to_get_n[value] = ways
    for value, ways in ways_to_get_n.items():
        if value + element not in new_ways_to_get_n:
            new_ways_to_get_n[value + element] = Paths(Node(i, ways), None)
        else:
            new_ways_to_get_n[value + element] = Paths(Node(i, ways), new_ways_to_get_n[value + element])
    ways_to_get_n = new_ways_to_get_n

完成后，ways_to_get_n[0]这是一个相当简洁的数据结构，可以使用双递归遍历包含第一个元素的所有分区。然而，有一个挑战。这些分区内部可能有 0 个分区。因此，当您沿着双递归进行时，请携带您可以达到的所有值的数据结构（相同的旧子集求和技巧），并在出现 0 时提前终止。（这种簿记可能感觉像是很多额外的工作，但它实际上会为您节省更多。）

现在您可以递归地找到具有第一个元素的最小分区。然后递归寻找如何划分剩余元素。每次你这样做时，你都会与你目前拥有的最好的进行比较，如果它是一种改进，请记录下来。

当你通过各种方式分解它时，你就完成了。

假设整数数组（因此子集和伪多项式可能对您有利），这将使您能够相当有效地在最小分区上进行递归。与幼稚的方法相比，这是一种更好的递归爆炸。但它会比你想象的要大得多。

我怀疑作为第一步以递增的绝对值对数组进行排序将使该算法更有效，因为当您仍然有很多元素时，“不可约分区的过滤器”可能会提前脱离递归。

于 2019-10-28T18:59:41.377 回答
1

我同意问题是NP。优化这个是丑陋的，大写的“呃”。您可以稍微改善搜索时间，但我担心它仍然是O(2^N)或更糟。

  • 将列表分成正数和负数；对两个列表进行排序。
  • 对于较短列表的每个元素，在另一个中寻找它的补码。每个这样的对都是一个分区；这些可以安全地放在解决方案列表中并从进一步处理中删除。

现在是丑陋的部分。“相对”的蛮力方法是生成每个分区的幂集；按总和索引。例如，给定列表2, 3, 4, 7：

 2  [2]
 3  [3]
 4  [4]
 5  [2, 3]
 6  [2, 4]
 7  [7] [3, 4]
 9  [2, 7] [2, 3, 4]
10  [3, 7]
11  [4, 7]
12  [2, 3, 7]
13  [2, 4, 7]
14  [3, 4, 7]
16  [2, 3, 4, 7]

现在在正负列表之间找到所有匹配的 abs(sum(subset)) 。这些构成了您的解决方案空间的选择。从这一点来看，我最好的建议是应用set coverage problem到这个；您必须稍微调整重复值。

于 2019-10-28T18:19:56.137 回答