当顺序很重要时如何解决硬币找零问题？

Question

如我在这里发现的，

Coin Change是找出使用给定面额d_1....d_m的硬币，总金额为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,1,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}是另一种具有不同顺序的组合。

- prime

---

你可以使用你的初始解决方案来生成唯一的集合，然后生成每个集合的所有排列以生成所有唯一的序列。 - mbeckish

你是否真的想要所有的解决方案，还是只想知道有多少个解决方案？ - Henry

@Henry 两种方法都可以。我想找到这个数字（例如，它是7）。如果我能打印出来也不会有问题。 - prime

@mbeckish：是的。如果我知道不同硬币价值的数量以及每个解决方案中它们出现的次数，那么这很容易。但是根据链接中给出的算法，它们只会计算答案（不同解决方案的总和），而不是逐个计算每个不同的解决方案。 - prime

Answer 1

仅计算解的数量比枚举所有解要简单得多。

以S={1,2,3}为例，将f(n)称为n金额的解数。

那么我们有：

如果n < 0，则f(n)=0

如果n=0，则f(0)=1

如果n > 0（其中1、2、3是S的元素），则f(n)=f(n-1)+f(n-2)+f(n-3)

编写执行这些计算的程序并不太困难。您可以从低数字开始并逐步增加：

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)种方式。因此，总数必须是三者之和。

- Henry

---

你正在使用递归解决方案计算重复值。例如{2,2}和{2,2}应该是1个排列而不是2个。你的方法仅适用于不同的元素。 - wckd

假设这是正确的，但如果S是动态分配的，我们可能事先不知道S。 - prime

@wckd 我认为那不正确。在计算 f(4) 中使用的术语之一是 f(4-2)，它基本上计算以 2 开头并后跟所有加起来等于 2 的序列。由于他对 f(2) 的计数没有将序列 {2} 计算两次，我不明白 f(4) 的计数如何包括 {2,2} 两次。 - ajb

@prime 我认为他的意思是 f(n) = f(n-S_1) + f(n-S_2) + ... + f(n-S_m)。在一般情况下，他关于“前三个数字”的最后一句话并不适用。 - ajb

@Henry，你的方程是否适用于更大的S集合，并且是否有某种证明或推导的链接？再次查看它，它看起来是正确的。我很抱歉。 - wckd

Answer 2

如果您指的是参考维基百科页面中的“动态规划”算法，我认为您只需更改。

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

to

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

但我还不确定。问题在于，在检查硬币S_j时，您希望添加可能解决方案的数量，当金额为i-S_j，但仅使用S_j及以前的硬币，这样您就不会得到以前序列的排列。通过将其更改为table [i-S_j，m]，您确实计算了排列。

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

- ajb

---

那么采用这种方法，这个做法是可行的吗？ {1,1,3} 不会认为 {1_a,1_b,3_a} 是一种组合，{1_b,1_a,3_a} 是另一种不同顺序的组合。 - prime

@prime 如果你问它是否会精确地计算 {1,1,3} 一次，我认为是的。但我还没有测试过。 - ajb

是的。这就是我所问的。这是一个重大关注点。谢谢你的回答。如果您有解决方案，请贡献一下，或请确认这个解决方案是否可行。 :) - prime

Answer 3

目前的递归实现非常简化。它只传递剩余值和可能面额的索引。如果在 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每次都被重置，所以它将遍历所有可能的排列。

- wckd

---

你能否详细解释一下这种方法？ - prime