algorithm - 适当的分区计数算法的解释？

Question

我一直在研究一些算法编程问题，并且对其中一个有疑问。该问题与此问题中引用的问题相同:USACO: Subsets (Inefficient)

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

问题(上面的链接)是:

Given a set of consecutive integers from 1 through N (1 <= N <= 39), how many ways can the set be partitioned into two subsets whose sums are identical? E.g., {1,2,3} can be partitioned one way: {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^0 项是一回事)(x^2+1/x^2)...(x^n+1/x^n)..."

任何人都可以为我澄清联系，或者给我一些解释这个具体问题的引用资料吗？谢谢。

Answer 1

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

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

这应该是显而易见的。

现在，让我们列出 S 的子集总和为 k , 对于任何 k和任何集合 S .任何这样的子集都必须有一个最大值，它必须是 S 的一个元素。 .最大值必须是 S 的最大元素, 或者它必须小于 S 的最大元素.这两组子集是截然不同的，所以我们可以分别枚举它们。我们称S的最大元素为S<sub>max</sub> .

第二组很简单:它只是 S - { S<sub>max</sub> } 的子集总和为 k .我们可以通过递归调用子集列表器来找到它们。但第一组几乎一样简单:组中的每个集合都包含 S<sub>max</sub>其余元素在 S - { S<sub>max</sub> } 中设置。加起来为 k - S<sub>max</sub> ，我们可以再次递归列出。为了完成递归，我们注意到如果 S是空集，那么如果 k = 0 ，恰好有一个合格子集(空集本身)，如果 k 不为 0，则没有合格子集。每次递归从 S 中删除一个元素, 因此最终必须达到终止条件。

应该清楚 S 的子集上面的递归函数将使用的只是来自 1 的数字至 S<sub>max</sub> , 所以我们可以去掉 S总而言之，递归写成如下:

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


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

Count_Subsets(min, max, k) = <br/>
  Count_Subsets(min, max - 1, k) <br/>
  + Count_Subsets(min, max - 1, k - max) <br/>


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

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

(事实上，很容易证明递归意味着当 k 递减到 1 时，值将为 0，如果 0 小于 k，则值为 0，因此我们可以使终止条件发生得更早。)

这为我们提供了简单的计数递归。但由于它调用自己两次，所以最好向后工作(“动态规划”)。我们需要计算 Count_Subsets(1, N, N*(N+1)/4) ，这将要求我们计算 Count_Subsets(1, max, k) 的值对于从 1 到 N 的所有 max 值，以及从 0 到 N*(N+1)/4 的所有 k 值。我们通过从 max = 0 开始，一直工作直到我们达到 min = N 来做到这一点。这正是您的算法所做的； i是max ，数组是 k 从 0 到 N(N+1)/4 的一组值.

顺便说一句，从上面的描述中应该很明显，a[j]应该增加 a[j - i] , 不是 a[j - 1]