动态规划的复杂组合条件 [英] Complex Combinatorial Conditions on Dynamic Programming

问题描述

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

为此，我正在研究硬币更改问题：让 S = [d_1，d_2，...，d_m] 和 n> 0 是请求的金额。

$ b我们可以用多少种方法只使用 S 中的元素加起来 n ？

如果我们采用动态编程方法来设计用于该问题的算法，该算法将允许多项式复杂度的解决方案，那么我们将从问题及其解决方法开始它与更小，更简单的子问题有关。这将产生一个递归关系，该递归关系描述了一个归纳步骤，该步骤用问题的相关子问题的解决方案来表示该问题。然后，我们可以实施 memoization 技术或制表技术，以分别以自上而下或自下而上的方式有效地实现此递归关系。

用于解决此问题实例的递归关系可以如下（Python 3.6语法和基于0的索引）：

  def C（S，m，n）：
如果n< 0：
返回0 
如果n == 0：
返回1 
如果m <= 0：
返回0 
 count_wout_high_coin = C（S ，m-1，n）
 count_with_high_coin = C（S，m，n-S [m-1]）$ ​​b $ b return count_wout_high_coin + count_with_high_coin 
  

此递归关系产生正确数量的解决方案，但不考虑顺序。但是，这种关系：

  def C（S，n）：如果n < 0：
返回0 
如果n == 0：
返回1 
返回总和（[C（S，n-coin）for S in coin]] 
  

在处理订单时会产生正确数量的解决方案。

我有兴趣通过可通过记忆/制表进一步优化的递归关系来捕获更多细微的组合模式。

例如，该关系：

  def C（S，m，n，p）：如果n< 0：
返回0 
如果n == 0而不是p：
返回1 
如果n == 0并且p：
返回0 
如果m == 0：
返回0 
返回C（S，m-1，n，p）+ C（S，m，n-S [n-1]，不是p）
  b 
 
产生一个不考虑阶数的解决方案，但仅计算具有偶数个求和项的解决方案。可以修改相同的关系以考虑顺序和计数偶数个数：
  def C（S，n，p ）：
，如果n< 0：
返回0 
如果n == 0而不是p：
返回1 
如果n == 0并且p：
返回0 
返回sum（[S中的硬币为C（S，n-硬币，不是p）]）
  
但是，如果我们有1个以上的人想要拆分硬币怎么办？假设我想将 n 分成2个人每个人获得相同数量的硬币，而不管每个人获得的总金额如何。在14种解决方案中，只有7种包含偶数个硬币，因此我可以将它们平均分配。但是我想排除给每个人多余的硬币分配。例如，当订单很重要时， 1 + 2 + 2 +1 和 1 + 2 +1 +2 是不同的解决方案，但它们将硬币拆分成两个人，即人 B 将得到 1 + 2 = 2 +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 。然后，如果我们将 n 分成可以分成两部分的所有方式，我们只需添加所有这些方式就可以用相同的数字 k 个硬币。
 
 
 
将我们选择的硬币子集固定到一个递减列表的好处在于，任何任意组合的硬币数量只会被计算一次-在计算中，组合中最左边的硬币是我们逐渐减少的子集中的第一个硬币（假设我们以相同的方式对其进行排序）。例如，任意子集 [6，24，48] ，取自 [1、2、6、12、24、48、60] ，将仅计入下一个子集<$ c的子集 [6、12、24、48、60] 的总和中$ c> [12、24、48、60] 将不包括 6 和上一个子集 [2、6 ，12，24，48，60] 至少有一个 2 硬币。
 
 
 
 Python代码（请在此处查看；确认此处）：
 导入时间
 
 def f（n，硬币）：
 t0 = time.time（）
 
 min_coins =分钟（硬币）
 
m = [[[0] * len（coins）for k in xrange（n / min_coins + 1）] for _n in xrange（n + 1）] 
 
＃初始化基本情况$在xrange（len（coins））中我的b $ b：
m [0] [0] [i] = 1 
 
f或i在xrange（len（coins））中：
对于xrange（i + 1）中的_i：
对于_n在xrange（coins [_i]，n + 1）：
对于k在xrange（1，_n / min_coins +1）中：
m [_n] [k] [i] + = m [_n-硬币[_i]] [k-1] [_ i] 
 
结果= 0 
 
对于xrange（1，n + 1）：
b = n-a 
 
对于xrange（1，n / min_coins + 1）：
结果=结果+ m [a] [k] [len（硬币）-1] * m [b] [k] [len（硬币）-1] 
 
 total_time = time.time（）-t0 
 
返回（结果，total_time）
 
打印f（500，[1、2、6、12、24、48 ，60]）
  
 
I am exploring how a Dynamic Programming design approach relates to the underlying combinatorial properties of problems.

For this, I am looking at the canonical instance of the coin change problem: Let S = [d_1, d_2, ..., d_m] and n > 0 be a requested amount. In how many ways can we add up to n using nothing but the elements in S?

If we follow a Dynamic Programming approach to design an algorithm for this problem that would allow for a solution with polynomial complexity, we would start by looking at the problem and how it is related to smaller and simpler sub-problems. This would yield a recursive relation describing an inductive step representing the problem in terms of the solutions to its related subproblems. We can then implement either a memoization technique or a tabulation technique to efficiently implement this recursive relation in a top-down or a bottom-up manner, respectively.

A recursive relation to solve this instance of the problem could be the following (Python 3.6 syntax and 0-based indexing):
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
This recursive relation yields a correct amount of solutions but disregarding the order. However, this relation:
def C(S, n):
  if n < 0:
    return 0
  if n == 0:
    return 1
  return sum([C(S, n - coin) for coin in S])
yields a correct amount of solutions while regarding the order.

I am interested in capturing more subtle combinatorial patterns through a recursion relation that can be further optimized via memorization/tabulation.

For example, this relation:
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)
yields a solution disregarding order but counting only solutions with an even number of summands. The same relation can be modified to regard order and counting number of even number of summands:
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])
However, what if we have more than 1 person among which we want to split the coins? Say I want to split n among 2 persons s.t. each person gets the same number of coins, regardless of the total sum each gets. From the 14 solutions, only 7 include an even number of coins so that I can split them evenly. But I want to exclude redundant assignments of coins to each person. For example, 1 + 2 + 2 + 1 and 1 + 2 + 1 + 2 are different solutions when order matters, BUT they represent the same split of coins to two persons, i.e. person B would get 1 + 2 = 2 + 1. I am having a hard time coming up with a recursion to count splits in a non-redundant manner.
解决方案
Here is a table implementation and a little elaboration on algrid's beautiful answer. This produces an answer for f(500, [1, 2, 6, 12, 24, 48, 60]) in about 2 seconds.

The simple declaration of C(n, k, S) = sum(C(n - s_i, k - 1, S[i:])) means adding all the ways to get to the current sum, n using k coins. Then if we split n into all ways it can be partitioned in two, we can just add all the ways each of those parts can be made from the same number, k, of coins.

The beauty of fixing the subset of coins we choose from to a diminishing list means that any arbitrary combination of coins will only be counted once - it will be counted in the calculation where the leftmost coin in the combination is the first coin in our diminishing subset (assuming we order them in the same way). For example, the arbitrary subset [6, 24, 48], taken from [1, 2, 6, 12, 24, 48, 60], would only be counted in the summation for the subset [6, 12, 24, 48, 60] since the next subset, [12, 24, 48, 60] would not include 6 and the previous subset [2, 6, 12, 24, 48, 60] has at least one 2 coin.

Python code (see it here; confirm here):
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])


                        
这篇关于动态规划的复杂组合条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！