问题标签 [coin-change]

最近我被分配了一个用 C++ 开发一个新项目的任务……我已经几天几夜都在思考如何处理它……不幸的是，这个想法没有成功，而且目前在设计阶段苦苦挣扎。基本上前提是：

“当地一家知名百货公司 Ruddles 的管理层已决定对整个商店的客户收银台进行某些更改。由于员工在为客户提供正确的零钱购买时存在问题，未来将自动从"

这只是有关业务本身的一些信息。以下是给我的需求规范：

并在任何给定面额的硬币数量低于某个值时发出警告。因此，您应该在您的解决方案中包含提供此类规定的设施。目前，硬件无法分发纸币，但未来的发展可能会使其成为可能，如果出现这些改进，您的解决方案应该能够应对这种情况。因此，您应该说明在发生此类硬件升级时需要对软件进行哪些更改。”

目前我真的不确定如何满足项目的以下要求，所以我只是想知道你们中是否有比我更有知识和经验的人可以提供一些建议或建议，这将非常感谢您的时间和关注:-)

我知道可能有多种方法可以解决这个问题，但到目前为止，我知道需要使用数组和持久性结构，尽管我不完全确定..

幸运的是，只要它完成这项工作，它就不必过度完成。我再次感谢您能给我的任何建议或提示。谢谢你。

给定一个总金额1.15 Rs.（1 Rs. = 100 Paise），所以总共 115 paise 并给出一个8 coins面额为paise 的列表{1, 2, 5, 10, 20, 25, 50, 100}。找出6 coins1.15 卢比的总和。限制是我不应该能够从我的解决方案中对受限集合中给出的金额进行更改。这里的限制集是{5, 10, 20, 25}。

感谢任何解决方案或指针。

我提前道歉。我知道之前有人问过这个问题，但答案并没有产生我想要/需要的结果。我正在尝试编写一个在 Python3 中执行以下操作的函数：

我需要一个递归函数，它返回产生指定数量的所有方式（硬币组合）。此函数只能包含两个参数，金额和硬币。我很难将注意力集中在递归上，因此也将不胜感激。谢谢。

这是我目前拥有的：

我完全陷入困境，不知道如何解决这个问题。假设我有一个数组

和一个数字

我需要 arr 中等于 n 的最短序列。因此，例如 arr 中的以下序列等于 n

因此，在上述情况下，我们的答案是 c2，因为它是 arr 中等于 sum 的最短序列。

我不确定找到上述解决方案的最简单方法是什么？任何想法或帮助将不胜感激。

谢谢！

编辑：

• 固定阵列
• 数组可能只有正值。
• 我不确定子集问题如何解决这个问题，可能是由于我自己的无知。子集算法是否总是给出等于和的最短序列？例如，子集问题会将 c2 识别为上述场景中的答案吗？

我有一个输入：

1. 测试用例的数量
2. 一笔钱

作为输出我需要：

1. 我们拥有的不同硬币的数量和每枚硬币的价值。

程序应该确定是否有解决方案，因此输出应该是“是”或“否”。

我使用动态编程编写程序，但它仅在我一次输入一个测试用例时才有效如果我一次编写 200 个测试用例，输出并不总是正确的。

我假设我在测试用例之间存在错误保存状态的问题。我的问题是，我该如何解决这个问题？我只是寻求一些建议。

这是我的代码：

您好，我在为学校作业创建零钱计算器时遇到问题。它本质上是计算一定数量的货币所需的最低变化量。

• 前任。5.36 美元：
• 2 个玩具（2 美元）
• 1加元（1美元）
• 1 季度
• 1毛钱
• 0 镍币
• 1便士

我已经声明我的所有变量都是双精度数，所以我可以一起计算值和总数。它似乎在整数（5.00、6.00、7.00）上运行良好，但每当我添加小数位时就会出错。就像当我说 5.25 美元时，它应该说 2 toonies 1 loonie 和 1 Quarter。我认为这可能是舍入错误或我的计算有问题。任何帮助表示赞赏。下面是代码的计算：

我基本上是在尝试通过递归来解决硬币找零问题，这就是我到目前为止所拥有的-：

第一个函数 s(i,sum) 由我编写，第二个函数 c(sum,i) 取自这里 - (www.algorithmist.com/index.php/Coin_Change)。

问题是 count 总是返回比预期更高的值。但是，算法专家的解决方案给出了正确的答案，但我无法理解这个基本情况

如果索引 (i) 小于或等于零并且总和仍然不为零，那么函数不应该返回零而不是一吗？

我也知道算法专家的解决方案是正确的，因为在Project Euler上，这给了我正确的答案。

我得到了一笔金额，比如 50 美元。我得到了一些面额，比如 1 美元、2 美元、5 美元等，这些面额的数量例如 1 、5、6 表示 1 枚硬币/1 美元的纸币、5 枚 2 美元的硬币/纸币和 6 枚 5 美元的硬币/纸币。我必须找出这些硬币可以用来形成这个 50 美元的数量。我试图想出一种有效的算法来尽可能快地解决这个问题。请注意，金额永远不会超过 60 美元。

有人可以建议我可以使用哪种算法来解决这个问题吗？到目前为止，我已经为这个问题编写了一个递归解决方案，但它对于我的目的来说太慢了。我很快就会在这里发布它。

样本输入：20 10 2 5 2

样本输出：2

说明：20的数量可以通过2种方式制作：10*2 10*1 + 5*2

我想找出用给定硬币制作特定数量的方法的数量。在示例输入中，20 是要制作的数量，下一行显示硬币价值和该价值的硬币数量，即 2 个有价值的硬币10.输出有20种可以用这些硬币制作的方法。我尝试了递归解决方案，但无法正常工作。我应该使用什么算法来解决这个问题？

出于某种原因，我总是得到 0 作为答案。请提供所有帮助。

该问题需要计算特定成本的硬币变化次数。

例如，如果我的硬币值为50, 20, 10, 5, 1，我可以形成以下成本：

5 => (5), (11111)，这是 2 种方式。

10 => (10), (5, 5), (5, 11111), (11111, 11111)，这是 4 种方式。

这是我的功能。它从 10 的成本中返回错误的结果（返回 9 种方式，而实际的方式只有 4 种）

如何修复此功能以提供正确数量的方式？这个算法是否正确？在此处查看完整的代码及其输出

注意：我的问题不在于dp数组初始化。我在每次调用之前都memset将其初始化为.-1rec