当订单很重要时，如何解决硬币兑换任务？

Question

正如我在这里发现的，

硬币兑换是指使用给定的一组面额d_1，找到对特定金额的美分、n进行兑换的方法的数量。。。。这是整数分割的一般情况，可以用动态规划来求解。

这个问题通常被问到：如果我们想改变N美分，并且我们有无限的S={S_1，S_2，......，S_m}价值的硬币，我们有多少种方法可以改变？（为了简单起见，顺序并不重要。）

我试过这个，效果很好。所以，当不同硬币的顺序确实重要时，我如何修改它来找到所有可能的硬币组合。

即：以前

例如，对于N=4，S={1,2,3}，有四个解：{1,1,1,1}，{1,1,2}，{2,2}，{1,3}。

现在：

对于N=4， S={1,2,3}，有7个解：{1,1,1,1}，{1,1,2}，{1,2,1}，{2,2}，{1,3}，{3,1}

在这里{1,1,1,1}即使可以按不同的顺序选择四个'1'，也必须将其视为一个最终组合。而不是考虑到四枚硬币是不同的。因此，实际上，不同硬币的顺序必须不同，才能将其作为单独的组合来计算。

例如：{1,1,3}不会假设{1_a，1_b，3_a}是一个组合，{1_b，1_a，3_a}是另一个具有不同顺序的组合。

Answer 1

当前的递归实现非常简单。它只传递剩余值和可能面额的索引。如果在n==0时传递了一个面额数组，则可以添加另一个检查以查看是否已经有了该组合。如果返回0，则返回1。

这是一个动态的解决方案，需要比其他解决方案多得多的内存，但它会为您找到答案。

func count(n, m, p[])
//regular if checks with additional nested if in (n == 0)
return count( n, m - 1, p[] ) + count( n - S[m], 0, p[] + S[m] )

在这个伪代码中，p[]S[m]只意味着将S[m]添加到p[]中的下一个可用位置

编辑：

忘记加了你下潜的时候需要重置m

// n is remaining value
// m is index of S array
// p[] is array of coins used
// solutions[] is an array of p[] arrays
func count( n, m, p[]) {
  if n == 0
    if (p[] not in solutions[]){
      solutions[].add(p[])
      return 1
    }else{
      return 0
    }
  if n < 0
    return 0
  if m <= 0 and n >= 1
    return 0
  return count(n, m - 1, p[]) + count( n - S[m], 0, p[].add(S[m]))
}

每次向可能的集合添加硬币时，从空数组p[]开始，将该值追加到数组。当你找到解决方案的时候，你会看到它是否独一无二。如果是这样，你把它添加到计数中，否则你会忽略它。因为m每次复位都会遍历所有可能的排列。

Answer 2

如果你在参考的维基百科页面中提到“动态规划”算法，我想你可以改变

table[ i, j ] = table[ i - S_j, j ] + table[ i, j - 1 ]

到

table[ i, j ] = table[ i - S_j, m ] + table[ i, j - 1 ]

但是我还不是100%确定。关键是在最初的问题中，当你检查硬币S_j时，你想在数量为i-S_j但只有硬币通过S_{j，这样就不会得到前一个序列的排列。通过将其更改为table[i-S_j， m]，您可以计算排列。}

编辑：进一步研究后，我认为这是正确的，但与亨利的答案相当，后者简单得多。这个版本的问题（计算所有排列）不需要像原始数组那样将值存储在二维数组中。

Answer 3

仅计算解决方案的数量比全部枚举要省力得多。

让我们以S={1,2,3}为例，调用f（n）数量n的解的数量。

然后我们有：

f（n）=0如果n

F（0）=1

f（n）=f（n-1）f（n-2）f（n-3）如果n

编写执行这些计算的程序并不太困难。你可以从低数字开始，然后逐步向上：

f(0) = 1
f(1) = 1
f(2) = 2
f(3) = 4
f(4) = 7
f(5) = 13
...

对于这个特殊的S，每个数字都是前面三个数字的和。

如何得出这个公式？我再次以特定的集合S={1,2,3}为例，一般情况同样简单。要计算n的解决方案数，请查看第一个元素。它可以是1、2或3。如果为1，则有f（n-1）种方式来排列剩余的元素。如果为2，则剩余元素有f（n-2）种方式，最后如果为3，则剩余元素有f（n-3）种方式。因此，总数必须是三者之和。