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

Question

我一直在研究一些算法编程问题并且有一个问题.问题与此问题中引用的问题相同:USACO:子集(低效)

我能够编写一些(非动态)解决方案,这些解决方案对于高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 ^ 0项(x ^ 1 + 1/x)(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 Smax

第二组很简单:它只是其总和的子集.我们可以通过递归调用子集列表来找到它们.但是,第一组是几乎一样简单:各组组中包括其要素的其他一些设置在其中加起来,这又可以递归地列出.为了完成递归,我们注意到如果是空集,那么如果,恰好有一个限定子集(空集本身),并且如果k不是0,那么就没有合格的子集.每次递归都会从中删除一个元素,因此最终必须达到终止条件.S - { Smax }kSmaxS - { Smax }k - SmaxSk = 0S

应该明确的是的子集S,将通过上述递归函数使用只是从数字1到,所以我们可以摆脱完全,并写出递归如下: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,那么我们可以使终止条件更早发生.)

这给了我们简单的递归计数.但由于它自称两次,因此倒退工作会更好("动态编程").我们需要计算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,并且数组是从0到0的k的值集N(N+1)/4.

顺便说一下,从上面的描述中可以明显看出,a[j]应该增加而a[j - i]不是增加a[j - 1]