硬币交换变体的动态规划解决方案

Question

我正在练习动态规划。我关注硬币交换问题的以下变体：

设S = [1, 2, 6, 12, 24, 48, 60] 为整数硬币面额的常数集。令 n 为可通过 S 中的硬币获得的正整数金额。考虑两个人 A 和 B。我可以用多少种不同的方式将 n 分配给 A 和 B 的人，以便每个人得到相同数量的硬币（忽略每个人实际得到的钱数）？

例子

n = 6每个人可以分成4种不同的方式：

人 A 得到 {2, 2}，人 B 得到 {1, 1}。
人 A 得到 {2, 1}，人 B 得到 {2, 1}。
人 A 得到 {1, 1}，人 B 得到 {2, 2}。
人 A 得到 {1, 1, 1}，人 B 得到 {1, 1, 1}。

请注意，每种方式对每个人来说都是非冗余的，即我们不将 {2, 1} 和 {1, 2} 都算作两种不同的方式。

之前的研究

我研究过非常相似的DP问题，比如硬币交换问题和分区问题。事实上，这个站点中的问题指的是几乎相同的问题：

Dynamic Programming for a variant of the coin exchange - 在这里，OP 研究了递归关系，但似乎对引入奇偶约束感到困惑。
Coin Change :Dynamic Programming - 在这里，OP似乎追求解决方案的重构。
Coin change(Dynamic programming) - 在这里，OP似乎也追求解决方案的重构。
https://cs.stackexchange.com/questions/87230/dynamic-programming-for-a-variant-of-the-coin-exchange-problem - 在这里，OP似乎问了一个类似的问题，但平价，即分裂成两个人，成为主要问题。

我最感兴趣的是可以帮助我解决这个问题的递归关系。定义它将使我能够轻松地应用制表方法的记忆来设计这个问题的算法。

例如，这个递归：

def f(n, coins):
  if n < 0:
    return 0

  if n == 0:
    return 1

  return sum([f(n - coin, coins) for coin in coins])

很诱人，但行不通，因为执行时：

# => f(6, [1, 2, 6]) # 14

这是 S' = {1, 2, 6} 和 n = 6 的运行示例，以帮助我阐明模式（可能有错误）：

Answer 1

这是您可以尝试的方法：

设 C(n, k, S) 是使用来自 S.

的一些 k 硬币数量 n 的不同表示的数量

然后 C(n, k, S) = sum(C(n - s_i, k - 1, S[i:])) 对 S 中的每个 s_i 求和。 S[i:] 表示从 S 开始的所有元素，从第 i 个元素到最后 - 我们需要它来防止重复组合。

初始条件为C(0, 0, _) = 1 and C(n, k, _) = 0 if n < 0 or k < 0 or n > 0 and k < 1 .

您要计算的数字：

R = sum(C(i, k, S) * C(n - i, k, S)) for i = 1..n-1, k = 1..min(i, n-i)/Smin 其中 Smin - 来自 S 的最小硬币面额。

值min(i, n-i)/Smin表示划分给定总和时可能出现的最大硬币数。例如，如果总和 n = 20 和 i = 8（第一个人获得 8 美元，第二个人获得 12 美元）并且最小硬币面额为 2 美元，则最大可能的硬币数量为 8/2 = 4。您无法用 >4 个硬币获得 8 美元。

Answer 2

这里有一个 table 实现和对的一些详细说明。这会在大约 2 秒内生成 f(500, [1, 2, 6, 12, 24, 48, 60]) 的答案。

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

将我们选择的硬币子集固定为递减列表的好处意味着任何硬币的任意组合都只会被计算一次——它将在计算中被计算，组合中最左边的硬币是第一个在我们递减的子集中投币（假设我们以相同的方式对它们进行排序）。例如，取自 [1, 2, 6, 12, 24, 48, 60] 的任意子集 [6, 24, 48] 只会计入子集 [6, 12, 24, 48, 60] 的总和，因为下一个子集 [12, 24, 48, 60] 不会包括 6 和前一个子集 [2, 6, 12, 24, 48, 60] 至少有一个 2 硬币。

Python代码（见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])

硬币交换变体的动态规划解决方案

Dynamic Programming Solution for a Variant of Coin Exchange

algorithm

recursion

dynamic-programming

coin-change