0

我想计算集合 S 中存在多少对不相交的子集 S1 和 S2（S1 U S2 可能不是 S），其中 S1 中的元素总和 = S2 中的元素总和。

假设我已经计算了所有可能的 2^n 子集的所有子集总和。我如何找到有多少不相交的子集具有相等的总和。

对于总和值 A，我们可以使用总和 A/2 的子集计数来解决这个问题吗？

例如：S ={1,2,3,4}

可能的各种 S1 和 S2 集是：

S1 = {1,2} 和 S2 = {3}

S1 = {1,3} 和 S2 = {4}

S1 = {1,4} nd S2 = {2,3}

这是问题的链接： http ://www.usaco.org/index.php?page=viewproblem2&cpid=139

4

2 回答 2

1

[编辑：修正了愚蠢的复杂性错误。谢谢卡什！]

实际上，我相信您需要使用此处描述的O(3^n)算法来回答这个问题 - O(2^n) 分区算法仅足以枚举其并集为整个的所有不相交子集对地套。

正如我链接到的答案中所述，对于每个元素，您基本上是在决定是否：

  1. 放在第一组，
  2. 将其放入第二组，或
  3. 忽略它。

考虑到所有可能的方法来生成一棵树，其中每个顶点有 3 个孩子：因此 O(3^n) 时间。需要注意的一点是，如果您生成一个解决方案 (S1, S2)，那么您不应该同时计算解决方案 (S2, S1)：这可以通过在构建它们时始终保持两组之间的不对称性来实现，例如强制 S1 中的最小元素必须始终小于 S2 中的最小元素。（这种不对称强制具有将执行时间减半的良好副作用:)）

特殊情况（但在实践中可能很常见）的加速

如果您预计集合中会有很多小数字，那么您可以使用另一种可能的加速：首先，按升序对列表中的所有数字进行排序。选择一些最大值 m，越大越好，但要足够小，以至于您可以负担 m 大小的整数数组。我们现在将数字列表分成两部分，我们将分别处理：一个初始数字列表，总和最多为 m（这个列表可能非常小），其余部分。假设前 k <= n 个数字适合第一个列表，并将这个第一个列表称为 Sk。原始列表的其余部分我们将称为 S'。

首先，将一个大小为 md[]的整数数组初始化为全 0，并像往常一样解决 Sk 的问题——但不是只记录具有相等和的不相交子集的数量，而是d[abs(|Sk1| - |Sk2|)]为每对不相交的子集 Sk1 和 Sk2 递增这些前 k 个数字。（d[0]当 Sk1 = Sk2 = 时，也会增加计数{}。）这个想法是，在第一阶段完成后，将记录从 S 的前 k 个元素生成d[i]2 个具有差异的不相交子集的方式数。i

其次，像往常一样处理余数（S'）——但不是只记录具有相等和的不相交子集的数量，而是|S1'| - |S2'| <= m将 加入d[abs(|S1'| - |S2'|)]到解决方案的总数中。这是因为我们知道有很多方法可以从具有这种差异的前 k 个元素构建一对不相交的子集——对于这些子集对中的每一个(Sk1, Sk2)，我们可以将 Sk1 或 Sk2 中的较小者添加到 S1 中的较大者中。 '或S2'，以及另一个到另一个，最终得到一对总和相等的不相交子集。

于 2013-10-22T00:08:46.400 回答
0

这是一个clojure解决方案。

它将 s 定义为 1、2、3、4 的集合然后所有子集定义为大小为 1 - 3 的所有集合的列表

一旦定义了所有子集，它就会查看所有子集对，并仅选择不相等、不与原始集合并集且总和相等的对

(require 'clojure.set)
(use 'clojure.math.combinatorics)

(def s #{1, 2, 3, 4})
(def subsets (mapcat #(combinations s %) (take 3 (iterate inc 1))))

(for [x all-subsets y all-subsets 
          :when (and (= (reduce + x) (reduce + y)) 
                     (not= s (clojure.set/union (set x) (set y))) 
                     (not= x y))] 
      [x y])

产生以下内容：

([(3) (1 2)] [(4) (1 3)] [(1 2) (3)] [(1 3) (4)])
于 2013-10-21T17:33:18.353 回答