我正在探索动态规划设计方法如何与问题的底层组合属性相关。
为此,我正在研究硬币找零问题的典型实例:设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 个人。无论每个人获得的总金额是多少,每个人都会获得相同数量的硬币。在 14 个解决方案中,只有 7 个包含偶数数量的硬币,这样我就可以平均分配它们。但我想排除向每个人分配多余的硬币。例如,当顺序很重要时,1 + 2 + 2 + 1
和 1 + 2 + 1 + 2
是不同的解决方案,但它们代表了两个人的相同硬币分配,即 B
会得到 1 + 2 = 2 + 1
。我很难想出一个以非冗余方式计算分割的递归。
最佳答案
(在详细阐述可能的答案之前,让我指出,计算硬币交换的分割数,即使是 n
,按总和而不是硬币-计数或多或少是微不足道的,因为我们可以计算交换 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
关于algorithm - 动态规划的复杂组合条件,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48809772/