algorithm - 动态规划的复杂组合条件

Question

我正在探索动态规划设计方法如何与问题的潜在组合属性相关联。

为此，我正在查看硬币找零问题的典型实例:令S = [d_1, d_2, ..., d_m] 和n > 0 是请求的数量。除了 S 中的元素外，我们可以通过多少种方式将 n 相加？

如果我们按照动态规划方法为这个问题设计一个允许多项式复杂度的解决方案的算法，我们将首先研究这个问题以及它与更小和更小的问题之间的关系更简单的子问题。这将产生一个递归关系，它描述了一个归纳步骤，根据相关子问题的解决方案来表示问题。然后，我们可以实现内存技术或制表技术，以分别以自上而下或自下而上的方式有效地实现这种递归关系。

解决此问题实例的递归关系可能如下(Python 3.6 语法和基于 0 的索引):

def C(S, m, n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    if m <= 0:
        return 0
    count_wout_high_coin = C(S, m - 1, n)
    count_with_high_coin = C(S, m, n - S[m - 1])
    return count_wout_high_coin + count_with_high_coin

此递归关系产生正确数量的解决方案，但忽略顺序。然而，这种关系:

def C(S, n):
  if n < 0:
    return 0
  if n == 0:
    return 1
  return sum([C(S, n - coin) for coin in S])

在考虑顺序时产生正确数量的解决方案。

我有兴趣通过可以通过内存/制表进一步优化的递归关系来捕捉更微妙的组合模式。

例如，这个关系:

def C(S, m, n, p):
    if n < 0:
        return 0
    if n == 0 and not p:
        return 1
    if n == 0 and p:
        return 0
    if m == 0:
        return 0
    return C(S, m - 1, n, p) + C(S, m, n - S[n - 1], not p)

产生一个不考虑顺序的解决方案，但只计算被加数为偶数的解决方案。可以修改相同的关系以考虑偶数个被加数的顺序和计数:

def C(S, n, p):
    if n < 0:
        return 0
    if n == 0 and not p:
        return 1
    if n == 0 and p:
        return 0
    return sum([C(S, n - coin, not p) for coin in S])

但是，如果我们要在不止 1 个人之间分配硬币怎么办？假设我想将 n 分成 2 个人 s.t.每个人得到相同数量的硬币，不管每个人得到的总金额是多少。在 14 个解决方案中，只有 7 个包含偶数个硬币，因此我可以将它们平均分配。但我想排除给每个人多余的硬币分配。例如，1 + 2 + 2 + 1 和 1 + 2 + 1 + 2 在顺序重要时是不同的解决方案，但它们对两个人表示相同的硬币分割，即人 B 会得到 1 + 2 = 2 + 1。我很难想出一个递归来以非冗余方式计算拆分。

Answer 1

(在我详细说明一个可能的答案之前，让我先指出计算硬币交换的 split ，对于偶数 n，按总和而不是硬币- count 或多或少是微不足道的，因为我们可以计算交换 n/2 并将其乘以自身的方式的数量:)

现在，如果您想根据硬币数计算硬币交换的拆分数，并排除给每个人多余的硬币分配(例如，拆分 1 + 2 + 2 + 1 分成两个大小相等的部分只有 (1,1) | (2,2)、(2,2) | (1,1) 或 (1,2) | (1,2) 并且每个部分中的元素顺序无关紧要)，我们可以依赖您对忽略顺序的分区的第一个枚举。

但是，我们需要知道每个分区中元素的多集(或相似元素的集合)，以便计算将它们一分为二的可能性。例如，要计算拆分 1 + 2 + 2 + 1 的方式，我们首先要计算每个硬币有多少:

def partitions_with_even_number_of_parts_as_multiset(n, coins):
  results = []

  def C(m, n, s, p):
    if n < 0 or m <= 0:
      return

    if n == 0:
      if not p:
        results.append(s)
      return

    C(m - 1, n, s, p)

    _s = s[:]
    _s[m - 1] += 1

    C(m, n - coins[m - 1], _s, not p)

  C(len(coins), n, [0] * len(coins), False)

  return results

输出:

=> partitions_with_even_number_of_parts_as_multiset(6, [1,2,6])
=> [[6, 0, 0], [2, 2, 0]]
                ^ ^ ^ ^ this one represents two 1's and two 2's

现在，由于我们正在计算选择其中一半的方式，因此我们需要在多项式乘法中找到 x^2 的系数

(x^2 + x + 1) * (x^2 + x + 1) = ... 3x^2 ...

表示从多重集计数[2,2]中选择两个的三种方式:

2,0 => 1,1
0,2 => 2,2
1,1 => 1,2

在 Python 中，我们可以使用 numpy.polymul 来乘以多项式系数。然后我们在结果中查找合适的系数。

例如:

import numpy    

def count_split_partitions_by_multiset_count(multiset):
  coefficients = (multiset[0] + 1) * [1]

  for i in xrange(1, len(multiset)):
    coefficients = numpy.polymul(coefficients, (multiset[i] + 1) * [1])

  return coefficients[ sum(multiset) / 2 ]

输出:

=> count_split_partitions_by_multiset_count([2,2,0])
=> 3