一种硬币交换变量的动态规划解法
我正在练习动态规划。我的重点是硬币交换问题的以下变体：
让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问题，例如硬币交换问题和分割问题。事实上，本网站中有一些问题涉及几乎相同的问题：
- 硬币交换变体的动态编程——在这里，OP研究了递归关系，但在引入奇偶约束时似乎很困惑。
- 硬币变化：动态编程-在这里，OP似乎追求解决方案的重建。
- 硬币变化（动态编程）-在这里，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的示例，以帮助我澄清模式（可能存在错误）：
共有2个答案
下面是一个表实现，并对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硬币制成的方式。
将我们从中选择的硬币子集固定到递减列表的美妙之处在于，任何任意的硬币组合都只会被计算一次——在计算中，组合中最左边的硬币是递减子集中的第一枚硬币（假设我们以同样的方式对它们进行排序）。例如，取自[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代码（请参见此处；请确认）：
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])
这是您可以尝试的：
让C（n， k， S）是使用S中的一些k硬币的数量n的不同表示的数量。
然后C（n， k， S）=和（C（n-s_i， k-1， S[i：]）求和是每个s_i从S.S[i：]表示所有元素从S开始从i-th元素结束-我们需要这样来防止重复的组合。
初始条件是C（0,0，）=1和C（n，k，）=0ifn
您要计算的数字：
R=sum（C（i，k，S）*C（n-i，k，S））fori=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。使用
-
我对解决硬币交换问题的一种变体感兴趣。回想一下硬币交换问题的正式定义： 给定一个值N，如果我们想改变N分，并且我们有无穷多的S={S1，S2，…，Sm}整值硬币，我们有多少种方法可以改变？硬币的顺序无关紧要。例如，对于N=4和S={1,2,3}，有四种解决方案：{1,1,1}，{1,1,2}，{2,2}，{1,3}。所以输出应该是4。对于N=10和S={2,5,3,6}，有五个解：{2,2,2,2
-
我编写的代码使用动态规划解决了基本的硬币兑换问题，并给出了进行兑换所需的最小硬币数量。但是我想把每个硬币的数量存储在最小的数字里。 我试图做的是初始化数组，就像散列一样，只要找到，它就会增加的数量，即。但这并不是我想要的方式，因为它每次发现对应于时都会添加硬币。因此，在最终答案中，数字不是硬币的最终计数。 代码如下：
-
但是我们不能这样做吗：（是给定的可用硬币的排序集，和是它的下标，是给定的最高价值硬币） 我写的东西有什么问题吗？虽然解决方案不是动态的，但不是更有效吗？
-
在硬币系统C={c1，c2，…ck}中，应改变给定的数量x，以使每个硬币ci具有给定的重量wi。我们想计算可能变化的总重量。两种变化是不同的，如果他们包含在不同的顺序相同的硬币。 如何给出上述问题的动态规划递归？我知道最小硬币兑换问题的递归（即C（x）=min{C（x-C）1 for x
-
问题-你会得到不同面额的硬币和总金额。写一个函数来计算你需要的最少数量的硬币来组成这个数量。那里有无限的硬币供应。 我的方法——我遵循了自上而下的方法，但是使用map stl进行记忆，我得到了TLE。请帮助找出误差和估计时间复杂度。 这是我的密码-
-
这是我关于硬币更换问题的代码，用于打印一组硬币的总方式数和目标金额 我想知道是否有任何方法可以用相同的动态规划解决方案打印这些方法（借助内部构造的表或任何其他方法） 例如，如果一组硬币是[1,3,5]，目标金额是6，那么总共有4种可能的方式。[1,1,1,1,1,1,1，]，[1,1,1,3]，[3,3]，[1,5]]我希望这种方式的列表作为输出。