确定给定金额的变更组合

Question

我的任务是使用强力写入算法来确定不同方式的数量,给定数量的相关变化组合.更改将使用以下硬币生产:便士(1美分),镍(5美分),角钱(10美分)和季度(25美分).

例如

输入:16(表示16美分的变化)

输出:可以通过6种不同的方式生成,它们是:

1. 16便士.
2. 11便士,1镍
3. 6便士,1角钱
4. 6便士,2镍
5. 1便士,3镍
6. 1便士,1镍,1角钱

我的算法必须为指定的更改量生成所有可能的更改组合.

---

关于如何开始这样的算法,我完全不知所措.让我前进的任何意见或见解都会很棒.

Answer 1

好的。让我解释一下蛮力算法的一个想法。我将在这里使用递归。

让我们需要改变c美分。然后考虑c为

c = p * PENNY + n * NICKEL + d * DIME + q * QUARTER

或者干脆，

c = ( p * 1 ) + ( n * 5 ) + ( d * 10 ) + ( q * 25 )

现在，你需要去通过所有可能的值p，n，d和q这等于价值c。使用递归，对于每个p in [0, maximumPennies]遍历每个n in [0, maximumNickels]. 对于每个n通过每个d in [0, maximumDimes]. 对于每个d通过每个q in [0, maximumQuarters].

p in [0, maximumPennies] AND c >= p
  |
  +- n in [0, maximumNickels] AND c >= p + 5n
       |
       +- d in [0, maximumDimes] AND c >= p + 5n + 10d
            |
            +- q in [0, maximumQuarters] AND c >= p + 5n + 10d + 25q

对于这些步骤中的任何相等性，您都有一个解决方案。