动态规划的复杂组合条件

Question

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

为此，我正在研究硬币兑换问题的典型实例：让S=[d_1，d_2，…，d_m]和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个人想要在其中分割硬币呢？假设我想在两个人之间分割ns. t.每个人得到相同数量的硬币，不管每个人得到的总和是多少。从14个解决方案中，只有7个包含偶数个硬币，这样我就可以均匀地分割它们。但是我想排除多余的硬币分配给每个人。例如，1 2 2 1和1 2 1 2在顺序问题上是不同的解决方案，但是它们代表两个人相同的硬币分割，即人B将得到1 2 = 2 1。我很难想出一个递归来以非冗余的方式计算分裂。




Answer 1

这里有一个表格实现，并对algrid的漂亮答案稍加阐述。这将在大约2秒内产生f（500，[1, 2, 6, 12, 24, 48, 60]）的答案。

C（n，k，S）=sum（C（n-S_i，k-1，S[i:]）的简单声明意味着使用k硬币添加所有获得当前总和的方法。然后，如果我们将n分成所有可以分成两部分的方式，我们只需添加所有这些部分可以由相同数量的k硬币制成的方式。

将我们选择的硬币子集固定到递减列表的美妙之处在于，任何任意的硬币组合都只会被计算一次——它将被计算在组合中最左边的硬币是我们递减子集中的第一枚硬币的情况下（假设我们以同样的方式订购）。例如，任意子集[6,24,48]，取自[1, 2, 6, 12, 24, 48, 60]，将只计算在子集[6, 12, 24, 48, 60]的求和中，因为下一个子集，[12, 24, 48, 60]将不包括6并且前一个子集[2, 6, 12, 24, 48, 60]至少有一个2硬币。

Python代码（在这里看到它；在这里确认）：

import time

def f(n, coins):
  t0 = time.time()

  min_coins = min(coins)

  m = [[[0] * len(coins) for k in xrange(n / min_coins + 1)] for _n in xrange(n + 1)]

  # Initialize base case
  for i in xrange(len(coins)):
    m[0][0][i] = 1

  for i in xrange(len(coins)):
    for _i in xrange(i + 1):
      for _n in xrange(coins[_i], n + 1):
        for k in xrange(1, _n / min_coins + 1):
          m[_n][k][i] += m[_n - coins[_i]][k - 1][_i]

  result = 0

  for a in xrange(1, n + 1):
    b = n - a

    for k in xrange(1, n / min_coins + 1):
      result = result + m[a][k][len(coins) - 1] * m[b][k][len(coins) - 1]

  total_time = time.time() - t0

  return (result, total_time)

print f(500, [1, 2, 6, 12, 24, 48, 60])

Answer 2

（在我详细阐述一个可能的答案之前，让我指出，即使是n，用总和而不是硬币计数来计算硬币交换的分割也或多或少是微不足道的，因为我们可以计算交换n/2的方法的数量并将其自身相乘：）

现在，如果您想根据硬币数量计算硬币交换的分割，并排除每个人的多余硬币分配（例如，将1 2 1分割为两个大小相等的部分只是（1,1）|（2,2），（2,2）|（1,1）或（1,2）|（1,2），每个部分中的元素顺序无关紧要），我们可以依赖于您的第一次分区枚举，其中顺序被忽略。

然而，我们需要知道每个分区中的多组元素（或相似元素的集合），以便计算将它们一分为二的可能性。例如，要计算分割方式，我们首先要计算每枚硬币的数量：

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