6

我一直在解决一些算法编程问题，并且有一个问题。问题与此问题中引用的问题相同：USACO: Subsets (Inefficient)

我能够编写一些对于高 N 来说太慢的（非动态）解决方案。不得不作弊并在线查找一些解决方案。事实证明，快速算法非常简单，但即使知道答案，我仍然看不出如何从问题中得到答案。我可以看到等和子集形成的模式，但我看不到这些模式与算法解决方案之间的联系。

问题（上面的链接）是：

给定一组从 1 到 N (1 <= N <= 39) 的连续整数，有多少种方法可以将该集合划分为两个总和相同的子集？例如，{1,2,3} 可以以一种方式分区：{1,2} {3}。

对于较大的集合，答案要么是 0（当 N*(N+1)/2 为奇数时），要么由以下简单算法给出：

  arr = array of int with (N*(N+1)/4)+1 elements
  arr[0]=1  // all other elements initialized to 0
  for i = 1 to N
    for j = N*(N+1) / 4 downto i
      add arr[j-i] to arr[j]
  subsetpaircount = arr[N*(N+1)/4] / 2

再一次，我可以看到算法是如何工作的，我什至插入了打印语句，所以我可以“观察”它是如何工作的。我只是看不出算法的操作如何与生成两组分区的不同方式的模式联系起来。

链接问题中的回答可能是相关的，但我也无法连接它是如何工作的：“这与在多项式 (x^1+1/x)(x) 中找到系数 x^0 项相同^2+1/x^2)...(x^n+1/x^n)..."

任何人都可以为我澄清联系，或者向我指出一些解释这个特定问题的参考资料吗？谢谢。

4

2 回答 2

7

如果该集合S = {1,...,N}被划分为两个总和相等的子集，则该总和必须是 的总和的一半S；的总和S是N(N+1)/2所以分区中每个子集的总和必须是N(N+1)/4。它也必须是整数，因此N(N+1)/2必须是偶数。

所以问题归结为找到总和为 的 S 的子集的数量N(N+1)/4。分区的总数正好是这个数字的一​​半，因为每个分区包含两个这样的子集，并且没有两个分区共享一个子集。

这应该是显而易见的。

现在，让我们列出任何和任何集合的S总和的子集。任何这样的子集都必须有一个最大值，它必须是 的一个元素。最大值必须是 的最大元素，或者必须小于 的最大元素。这两组子集是不同的，所以我们可以分别列举出来。我们称 为 的最大元素。kkSSSSS Smax

第二组很简单：它只是总和为的子集。我们可以通过递归调用子集列表器来找到它们。但是第一组几乎一样简单：组中的每个集合都包括，其其余元素是一些集合，其中加起来为，我们可以再次递归列出。为了完成递归，我们注意到 if是空集，那么 if ，恰好有一个合格子集（空集本身），如果 k 不为 0，则不存在合格子集。每次递归都会从 中删除一个元素，因此最终必须达到终止条件。S - { Smax }kSmaxS - { Smax }k - SmaxSk = 0S

应该清楚，S上述递归函数将使用的子集只是从1to的数字，因此我们可以完全摆脱，并将递归编写如下：SmaxS

Subsets(min, max, k) =
  Subsets(min, max - 1, k)
  ⋃ { {max, P} | P ∈ Subsets(min, max - 1, k - max) }

但是我们只想要分区数的计数，所以我们可以稍微简化一下：

Count_Subsets(min, max, k) =
  Count_Subsets(min, max - 1, k)
  + Count_Subsets(min, max - 1, k - max)

我们需要通过添加结束条件来完成递归：

If min > max, Count_Subsets(min, max, k) = 1 if k = 0; otherwise 0

（事实上​​，很容易证明递归意味着1当 k 递减到0并且0如果k小于时该值将是0，因此我们可以使终止条件更早发生。）

That gives us the simple recursion for the count. But since it calls itself twice, it would be better to work backwards ("dynamic programming"). We need to compute Count_Subsets(1, N, N*(N+1)/4), which will require us to compute values of Count_Subsets(1, max, k) for all values of max from 1 to N, and from all values of k from 0 to N*(N+1)/4. We do that by starting with max = 0, and working up until we reach min = N. And that's precisely what your algorithm does; i is max, and the array is the set of values for k from 0 to N(N+1)/4.

By the way, as should be apparent from the above description, a[j] should be incremented by a[j - i], not by a[j - 1]

于 2013-01-24T23:09:26.237 回答
1

我认为您的伪代码中可能有一个错误导致了混乱。我希望这条线

add arr[j-1] to arr[j]

成为

add arr[j-i] to arr[j]

假设是这种情况，那么考虑这个问题的方法是，在 i 上循环的每次迭代开始时，数组 arr[j] 包含选择整数 1,2 的子集的方法数， ...,i-1 使得所选整数的总和正好是 j。

开始时，i=1，因此子集的唯一选择是总和等于 1 的空子集。

这就是为什么 arr[0]=1（表示使用空子集得到总和为 0）而所有其他条目为 0（因为无法获得非零和）的原因。

从那时起，每次迭代都考虑将数字 i 添加到子集中。获得总和 j 的方法的数量取决于是否包含 i。

如果 i 不包括在内，那么我们有与以前相同数量的方式（即 arr[j]）。

如果包含 i，那么为了得到包含 i 的 j 的总和，我们必须将 i 添加到 1,..,i-1 的所有子集，这些子集的总和为 ji。按照设计，如果我们查看索引 ji，我们的数组正好包含这个数字。

所以得到j和的方法总数变成arr[j]+arr[ji]。

当 i 循环完成时，arr 会为您提供选择子集并获得所需总和的方法的数量。我们知道 1,2,..,n 的总和是 n*(n-1)/2，所以如果我们计算有多少子集达到该值的一半，那么我们将分区计算为相等的总和。

实际上，这多算了 2 倍，因为它将 {1,2}/{3] 和 {3}/{1,2} 计为单独的解决方案，因此最终答案除以 2。

于 2013-01-24T23:04:10.040 回答