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

Question

我正在练习动态编程。我专注于硬币交换问题的以下变体：

让S = [1, 2, 6, 12, 24, 48, 60]成为一组恒定的整数硬币面额。让n成为通过S中的硬币可获得的正整数金额。考虑两个人A和B。在多少种不同的方式我可以在n和A之间拆分B，以便每个人获得相同数量的硬币（无视每个人获得的实际金额）？

例

n = 6可以分为4种不同的方式：

1. 人A获得{2,2}，人B获得{1,1}。
2. 人A获得{2,1}，人B获得{2,1}。
3. 人A获得{1,1}，人B得到{2,2}。
4. 人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)使用来自n的一些k硬币，数量S的不同表示。

然后C(n, k, S) = sum(C(n - s_i, k - 1, S[i:]))总和是来自s_i的每个S。 S[i:]是指S从i-th元素到结尾的所有元素 - 我们需要这个来防止重复组合。

如果C(0, 0, _) = 1或C(n, k, _) = 0或n < 0和k < 0，最初的条件是n > 0和k < 1。

您要计算的数字：

qazxsw poi for qazxsw poi，qazxsw poi R = sum(C(i, k, S) * C(n - i, k, S)) - i = 1..n-1最小的硬币面额。

值k = 1..min(i, n-i)/Smin表示分割给定总和时可能的最大硬币数。例如，如果总和Smin和S（第一人获得8美元，第二人获得12美元）并且最小硬币面额是2美元，则最大可能的硬币数量是min(i, n-i)/Smin。你不能用n = 20硬币获得8美元。

Answer 2

这是一个表实现和i = 8的一点点阐述。这会在大约2秒内为8/2 = 4产生答案。

>4的简单声明意味着使用algrid's beautiful answer硬币添加所有方法来获得当前总和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的总和，因为下一个子集，[6, 24, 48]将不包括[1, 2, 6, 12, 24, 48, 60]，并且先前子集[6, 12, 24, 48, 60]具有至少一个[12, 24, 48, 60]硬币。

Python代码（见6;确认[2, 6, 12, 24, 48, 60]）：

2