问题标签 [coin-change]

我正在寻找最有效的方法来从购买金额中计算出零钱金额（夸脱、角钱、镍币和便士）。购买金额必须小于 1 美元，零钱从 1 美元起。我需要知道有人能拿回多少 25 美分硬币、5 美分硬币和多少便士。

最好是建立一本字典吗？

我发现了一段我几个月前为面试准备而编写的代码。

根据我的评论，它试图解决这个问题：

给定一些以美分为单位的美元价值（例如 200 = 2 美元，1000 = 10 美元），找出构成美元价值的所有硬币组合。只允许使用便士 (1¢)、镍 (5¢)、10 美分 (10¢) 和 25 美分 (25¢)。

例如，如果给出 100，答案应该是：

我相信这可以通过迭代和递归的方式来解决。我的递归解决方案有很多错误，我想知道其他人将如何解决这个问题。这个问题的难点在于使其尽可能高效。

所以; 我是一个正在尝试通过 SICP 工作的爱好者（它是免费的！），第一章中有一个示例程序，旨在计算用美国硬币找零的可能方法；(change-maker 100) => 292. 它的实现如下：

反正; 这是一个树递归过程，作者“作为一个挑战离开”找到一个迭代过程来解决相同的问题（即固定空间）。在感到沮丧之后，我没有运气弄清楚这一点或找到答案。我想知道这是我的脑放屁，还是作者在和我开玩笑。

我想知道每个面额都有无限数量的硬币的硬币找零问题的算法思想。表示如何应用 DP（如标准硬币找零问题） 例如，在第 1、10、15 组中，找零 35 给--2 个 10 硬币和 1 个 15 硬币

也给我一个蛮力算法的想法。我知道迭代所有的集合。但是如何在暴力破解时改变每个硬币的数量

我最近才开始学习 Objective-C（或相关的编程）并且被困在一个简单的程序上。

我试图创造硬币、硬币、镍币和便士的变化，但注意到我提出的解决方案会给镍币或便士随机赋予价值。

前任。25 的变化会变成“变化是 1 季度，0 角钱，-1881139893 镍币和 4096 便士”

例 2。30 的零钱会变成“零钱是 1 夸特，0 角钱，1 镍币和 4096 便士”

我可以添加/更改什么来解决此问题？

另外，有没有更好的解决方案，然后必须运行 4 个不同的 if 语句？

谢谢！

下面是我的代码：

您好，我正在尝试创建一个算法来找出我可以通过多少种方式找回零钱。但我就是无法正确执行，我一直得到 4，而我应该得到 6，我就是不明白为什么。

这是我在 C# 中的实现，它是从http://www.algorithmist.com/index.php/Coin_Change的伪代码创建的

我编写了一个用于生成子集总和的程序，该程序可用于此问题，其中指出：

假设你有 3 个 1 美元硬币、2 个 2 美元硬币、3 个 5 美元硬币、1 个 10 美元硬币，有 4 种方法可以从这些硬币中获得 10 美元。如果有 n1 个 $X1 个硬币，n2 个 $X2 个硬币...... nm $Xm 个硬币，我们有多少种方法可以从这些有限数量的硬币中获得 $X？

如果我们创建一组 { X1, X1..... X1, X2, X2.......... X2, ..., ..., .... .., Xm, Xm... Xm}，然后对它运行子集求和，当然我们可以得到 $X 的结果。但我找不到使用集合 {n1, n2, n3.... nm} , {X1, X2, X3.... Xm} 的方法。一位朋友告诉我，这是背包问题的变体，但我不确定如何。

这是我写的部分代码：

如果您能详细解释一下，那对我来说会很棒。

编辑：这个问题更适合用于计算机科学的 stackexchange，但由于这是我的一个老问题，我宁愿在这里编辑它。

这个问题可以通过包含排除原则来解决，当我们将硬币值固定但每个硬币的数量随每次查询而变化时，它会派上用场。

假设，ways[v]是用$x1，$x2， .. $xm制作$v的方法，每个都可以根据需要多次使用。现在，如果我们只使用n1个$x1数字，我们必须使用至少 ( n1 + 1) 个$x1数字减去配置（这实际上是方式[ v - (n1 + 1)x1 ] ）。此外，如果我们只使用$x2的n2个数字，我们还必须减去方式[ v - (n2 + 1)x2 ]，等等。

现在，我们已经两次减去至少使用 ( n1 + 1) $x1和 ( n2 + 1) $x2的配置，因此我们需要添加方式[ v -(n1 + 1)x1 - (n2 + 1) x2 ] 等。

特别是，如果，

N = 尽可能多地使用所有硬币的一组配置，

Ai = 至少使用ni + 1 个$xi的配置集，对于 1 <= i <= m，则

我们正在寻求的结果 = | N | - | A1 | - | A2 | .. - | 上午| + | A1和A2 | + | A1和A3 | + ... - | A1和A2和A3 | ......

计算无限硬币配置数量的代码实际上更简单：

嘿大家。我有个问题。我正在使用 Visual Basic Express，我应该计算交易的变化。

现在我会使用什么代码？我让它部分工作，但它开始变得有点混乱。

谢谢你。

对于想要更多信息的你们：

假设我有一美元，我去商店买东西。我必须要求用户输入他们花费的金额，然后计算变化并打印到屏幕上。

然后我应该使用最少数量的 25 美分硬币和硬币并将其打印到屏幕上。

任何帮助将不胜感激。

我正在尝试创建“make-change”，它将返回总和 = 输入的硬币的 ls，并且它需要包含尽可能少的硬币数量。例如：（修改 99）

=> （四分之一四分之一一角一角便士便士便士便士便士）

是的，我知道有与此类似的帖子，但是在浏览完所有帖子后，我仍然被困住，因为我对编程很陌生，而且给出的答案都不足以针对我的问题提供帮助。

问题。编写一个有效的 ACL（算法计算机语言）算法，给定一件物品的成本（小于或等于 1 美元），给出购买者想要的 50 美分、20 美分、10 美分、5 美分和 1 美分硬币的数量如果他们交出一美元，就会收到。您必须尽量减少找零中的硬币数量。

该问题与任何特定的编程语言无关，答案只能使用简单的 ACL 语言，如 if、if-else、while 循环，不能使用数组或其他高级命令。

这是我所在的位置：

在此处输入代码算法最小更改量

代码完成，感谢您的帮助！如果您发现任何歧义或可以帮助我简化代码，请告诉我。