问题标签 [coin-change]

我正在尝试解决这个问题：

假设我有一组 n 个硬币 {a_1, a2, ..., a_n}。价值为 1 的硬币总是会出现。我需要达到 M 的最少硬币数量是多少？

约束是：

• 1≤n≤25
• 1≤m≤10^6
• 1 ≤ a_i ≤ 100

好的，我知道这是变革问题。我尝试使用广度优先搜索、动态规划和贪婪来解决这个问题（这是不正确的，因为它并不总是提供最佳解决方案）。但是，我超过了时间限制（3 秒）。

所以我想知道是否有针对这个问题的优化。描述和限制引起了我的注意，但我不知道如何使用它对我有利：

• 价值为 1 的硬币总是会出现。
• 1 ≤ a_i ≤ 100

我在维基百科上看到这个问题也可以通过“使用概率卷积树进行动态编程”来解决。但我什么都听不懂。

你能帮助我吗？这个问题可以在这里找到：http: //goo.gl/nzQJem

我试图用 M=10、c={5,3,1} 和 d=3 来追踪硬币找零问题的递归算法。M 是需要找零的货币价值，c 是可用的不同硬币价值，d 是可用的不同硬币价值的数量。我对如何追踪它感到困惑。

RecursiveChange(M,c,d)

调用 1：RecursiveChange(10, {5, 3, 1}, 3)

调用 2：RecursiveChange(5, {5, 3, 1}, 3)

调用 3：RecursiveChange(0, {5, 3, 1}, 3)

在调用 3 中，由于 M=0，将返回 0。我的理解是：0 返回到调用 2。然后，从调用 2 继续，运行以下部分：

其中 bestNumCoins 将取值 1。然后将这个值 1 返回给调用 1。然后，从调用 1 继续，因为 numCoins + 1（即 2）不 < bestNumCoins（即 1），bestNumCoins 将保持为 1，并且然后这个值 1 将是最终值。首先，我认为 2 应该是这里的最终值，因为要获得 10 个单位，需要两个价值 5 的硬币。

我需要帮助来解决这个问题，拜托。我已经花了好几个小时了。

我在编写的代码中收到 std::bad alloc() 异常。根据 SO 上的其他答案，我应该释放动态分配的内存，但异常仍然存在。关于我如何解决它的任何线索？

我正在附加错误出现的功能。

int count(int *S, int m, int n) { int i, j, x, y;

我基本上是在尝试解决硬币兑换问题。n 可以大到 10^9。

您好，我在编写此函数时遇到问题。

目标是编写一个函数来计算找零所需的最少硬币数量。该函数必须使用递归，并且您不能使用任何类型的循环。

我在这个问题上遇到很多麻烦的原因是返回类型是所有硬币的结构：

该函数如下所示：

这是一个家庭作业问题，所以我不是在寻求答案，但我只是在试图弄清楚这个问题的基本案例应该是什么时遇到了很多麻烦。这是我到目前为止所拥有的：

谢谢！

我想找到硬币找零的所有组合。1、2、5、10、20、50、100 和 200。（1 美分、2 美分 ..）如果硬币超过 500（5 欧元），它应该给 -1。我的代码与这些测试用例完美配合：numOfSplits 10 (11) numOfSplits 20 (41) numOfSplits 100 (4563)。当我尝试使用测试用例 numOfSplits 200 或 500 时，它会给出 C 堆栈溢出错误。我怎样才能使我的代码更好？

我将代码更改为此代码，并且不再出现堆栈溢出错误，但现在我的代码运行缓慢。示例：对于 numOfSplits 500 ，它的时间超过 30 分钟，我怎样才能更快地做到这一点？

我在理解动态编程中的硬币变化问题时遇到了一个小问题。简而言之，我必须使用最少数量的硬币来更改金额。

我有 n 个面额为 1 = v1 < v2 < ... < vn 的硬币，我们记下 M(j) 为金额 j 找零所需的最小硬币数量。

在上面的公式中，我不明白 M(j-vi) 是什么意思。vi 必须是 j-1 中使用的硬币的最大值吗？

我是一名初学者，学习麻省理工学院 OpenCourseWare 上的 SICP 课程，同时使用视频讲座和在线书籍。昨天我遇到了一个例子，它询问我们是否可以编写一个程序来计算改变任何给定金额的方法的数量。

这个问题有一个简单的递归过程解决方案：

如果你想查看更多，我从这里拿走了。

他们正在计算使用 K 种硬币改变数量 (A) 的方法的数量 (N)，方法是添加：

1. 在没有第一类硬币的情况下改变 A 的方式数 (X)。

2. 改变 (A - D) 的方式 (Y) 的数量，其中 D 是第一枚硬币的面额，使用所有 K 种硬币。

问题是，我只是不明白这一点。接下来，他们试图解释说：

“要了解为什么这是真的，请观察做出改变的方式可以分为两组：不使用任何第一种硬币的那些，以及使用任何一种硬币的那些。因此，做出改变的方式的总数for some amount 等于不使用任何第一种硬币的金额的找零方式的数量，加上假设我们使用第一种硬币的找零方式的数量。（是最后一句与加法相同 N = X + Y ?)但后一个数字等于使用第一种硬币后剩余金额的找零方式的数量。（使用此硬币后，他们指的是方式用或不用第一种硬币找零？） ”

我了解他们如何实现递归算法，但我无法看到他们是如何到达那里的。英语不是我的母语，所以我可能会遗漏一些东西。如果您能用其他术语向我解释解决方案背后的逻辑，我将不胜感激。谢谢。

我需要帮助找到以下算法的渐近运行时间，即 Big O(n) -> change_slow() 。我尝试了大师方法和其他技术，但似乎找不到答案。

这是一个硬币找零问题，使用以下数据范围处理：

这是算法：

T(n) = 形式的方程是什么？

在以下贪心算法的找零问题中，解决以下问题：如何用最少数量的硬币赚到给定数量的钱？

算法：尽可能使用最有价值的硬币。假设我们有无限数量的每组硬币。

我的教授，写的（4）没有产生最佳解决方案，任何人都可以说为什么？（或者为什么其他不是反例？）

我在理解各种问题的动态编程解决方案方面遇到问题，特别是硬币找零问题：

“给定一个值 N，如果我们想找 N 美分，并且我们有无限供应 S = { S1, S2, .. , Sm} 价值的硬币，我们有多少种方法可以找零？顺序硬币没关系。

例如，对于 N = 4 和 S = {1,2,3}，有四种解：{1,1,1,1},{1,1,2},{2,2},{1, 3}。所以输出应该是 4。对于 N = 10 和 S = {2, 5, 3, 6}，有五种解决方案：{2,2,2,2,2}，{2,2,3,3}， {2,2,6}、{2,3,5} 和 {5,5}。所以输出应该是 5。”

这个问题还有另一种变体，其中解决方案是满足数量的最小硬币数量。

这些问题看起来非常相似，但解决方案却大不相同。

进行更改的可能方法的数量：对此的最佳子结构是DP(m,n) = DP(m-1, n) + DP(m, n-Sm)其中 DP 是所有硬币的解决方案数第 m 个硬币和金额 = n。

最小硬币数量：最佳子结构是 DP[i] = Min{ DP[i-d1], DP[i-d2],...DP[i-dn] } + 1其中 i 是总金额d1..dn 代表每个硬币面额。

为什么第一个需要二维数组而第二个需要一维数组？为什么改变方法数量的最佳子结构不是“ DP[i] = DP[i-d1]+DP[i-d2]+...DP[i-dn] ”，其中 DP[i] 是i 数量可以通过硬币获得的方式数量。这对我来说听起来合乎逻辑，但它会产生一个不正确的答案。为什么在这个问题中需要硬币的第二维，但在最小数量问题中不需要？

问题链接：

http://comproguide.blogspot.com/2013/12/minimum-coin-change-problem.html http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

提前致谢。我访问的每个网站都只解释解决方案的工作原理，而不是为什么其他解决方案不起作用。