总和相等的子集 [英] Subsets with equal sum
问题描述
我想计算集合S中有多少对不相交的子集S1和S2（S1 U S2可能不是S），其中S1中的元素之和= S2中的元素之和。
I want to calculate how many pairs of disjoint subsets S1 and S2 (S1 U S2 may not be S) of a set S exists for which sum of elements in S1 = sum of elements in S2.
说我已经计算了所有可能的2 ^ n个子集的所有子集和。
我如何找到多少个不相交的子集具有相等的总和。
Say i have calculated all the subset sums for all the possible 2^n subsets. How do i find how many disjoint subsets have equal sum.
对于总和值A，我们可以使用具有总和A / 2的子集的数量来解决吗？
For a sum value A, can we use the count of subsets having sum A/2 to solve this ?
例如：
S = {1,2,3,4}
As an example : S ={1,2,3,4}
各种S1和S2集可能是：
Various S1 and S2 sets possible are:
S1 = {1,2}和S2 = {3}
S1 = {1,2} and S2 = {3}
S1 = {1,3}和S2 = {4}
S1 = {1,3} and S2 = {4}
S1 = {1,4}和S2 = {2,3}
S1 = {1,4} nd S2 = {2,3}
此处是链接问题：
http://www.usaco.org/ index.php？page = viewproblem2& cpid = 139
推荐答案
实际上，我相信您需要使用 O（3 ^ n）算法在此处描述以回答此问题-O（2 ^ n）分区算法仅足以枚举所有不相交的子集对谁的联合是整个地面集。
Actually I believe you'll need to use the O(3^n) algorithm described here to answer this question -- the O(2^n) partitioning algorithm is only good enough to enumerate all pairs of disjoint subsets whose union is the entire ground set.
正如我所链接的答案所述，对于每个元素，您基本上都在决定是否：
As described at the answer I linked to, for each element you are essentially deciding whether to:
- 将其放入第一组，
- 将其放入第二组，或
- 忽略它。
考虑到每种可能的方式，都会生成一棵树，其中每个顶点有3个子代：因此O（3 ^ n）时间。需要注意的一件事是，如果您生成一个解（S1，S2），那么您也不应同时计算该解（S2，S1）：这可以通过在构建它们时始终保持两个集合之间的不对称来实现，例如强制S1中的最小元素必须始终小于S2中的最小元素。 （这种不对称执行具有将执行时间减半的不错的副作用：））
Considering every possible way to do this generates a tree where each vertex has 3 children: hence O(3^n) time. One thing to note is that if you generate a solution (S1, S2) then you should not also count the solution (S2, S1): this can be achieved by always maintaining an asymmetry between the two sets as you build them up, e.g. enforcing that the smallest element in S1 must always be smaller than the smallest element in S2. (This asymmetry enforcement has the nice side-effect of halving the execution time :))
如果您希望集合中有很多小数字，那么您还可以使用另一种加速方法：首先，对所有列表中的数字按升序排列。选择一些最大值m，越大越好，但又足够小，您可以负担一个m大小的整数数组。现在，我们将数字列表分为两部分，分别处理：一个初始数字列表，其总数最多为m（此列表可能很小），其余部分则为。假设前k个<= n个数字适合第一个列表，并将其称为第一个列表Sk。
If you expect that there will be many small numbers in the set, there is another possible speedup available to you: First, sort all the numbers in the list in increasing order. Choose some maximum value m, the larger the better, but small enough that you can afford an m-size array of integers. We will now break the list of numbers into 2 parts that we will process separately: an initial list of numbers that sum to at most m (this list may be quite small), and the rest. Suppose the first k <= n numbers fit into the first list, and call this first list Sk. The rest of the original list we will call S'.
首先，初始化一个size-m数组 d [] 将所有整数都设为0，并像往常一样解决Sk的问题-而不是仅记录具有相等总和的不相交子集的数目，而是增加 d [abs（| Sk1 |-| Sk2 |） ] 表示由这前k个数组成的每对不相交子集Sk1和Sk2。 （也可以增加 d [0] 来计算Sk1 = Sk2 = {} 的情况。）这个想法是在第一个阶段完成之后， d [i] 将记录2个相异的子集的方式数目，这些子集的差异小于 i 可以从S的前k个元素生成。
First, initialise a size-m array d[] of integers to all 0, and solve the problem for Sk as usual -- but instead of only recording the number of disjoint subsets having equal sums, increment d[abs(|Sk1| - |Sk2|)] for every pair of disjoint subsets Sk1 and Sk2 formed from these first k numbers. (Also increment d[0] to count the case when Sk1 = Sk2 = {}.) The idea is that after this first phase has finished, d[i] will record the number of ways that 2 disjoint subsets having a difference of i can be generated from the first k elements of S.
第二，照常处理其余（S'），而不是仅记录不相交的数目每当 | S1'|时，子集具有相等的和-| S2’| < = m ，在解决方案总数中添加 d [abs（| S1'|--| S2'|）] 。这是因为我们知道有很多方法可以从前k个具有此差异的元素中构建一对不相交的子集-对于每个子集对（Sk1，Sk2），我们可以将Sk1或Sk2中的较小者添加到S1'或S2'中的较大者，并将另一个添加到另一个，以得出一对具有相等总和的不相交的子集。
Second, process the remainder (S') as usual -- but instead of only recording the number of disjoint subsets having equal sums, whenever |S1'| - |S2'| <= m, add d[abs(|S1'| - |S2'|)] to the total number of solutions. This is because we know that there are that many ways of building a pair of disjoint subsets from the first k elements having this difference -- and for each of these subset pairs (Sk1, Sk2), we can add the smaller of Sk1 or Sk2 to the larger of S1' or S2', and the other one to the other one, to wind up with a pair of disjoint subsets having equal sum.
这篇关于总和相等的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
