问题标签 [coin-change]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
3 回答
16092 浏览

python - 递归变更算法

给定目标金额和硬币面额列表,我的代码应该找到达到目标金额所需的最少硬币。

例子:

  • C(78, [1, 5, 10, 25, 50]) = 6

    • 我们可以从 3x 25+ 3x得到 78 1,所以需要 6 个硬币
  • C(48, [1, 7, 24, 42]) = 2

    • 48 = 2x 24,所以 2 个硬币就足够了
  • C(35, [1, 3, 16, 30, 50]) = 3

    • 我们可以从 2x 16+ 1x得到 35 3,所以 3 个硬币就足够了

我用 for 循环编写了代码,但是如何让它递归呢?

0 投票
2 回答
796 浏览

algorithm - 如果我使用动态规划来解决硬币找零,那么用于记忆的矩阵将是什么?

我对硬币问题的动态编程技术的矩阵应该是什么样子感到困惑。假设我有 1c、5c、10c 和 25c 的面额,我称之为 make-change(10)。即我想为 10 美分进行更改,我的最终矩阵/数组应该是什么样子。我需要知道这一点,因为我想在程序的开头分配一个数组。我不是在这里寻找代码。

0 投票
1 回答
1123 浏览

algorithm - 印刷硬币图案

可能重复:
递归进行更改:如何修改我的算法以打印所有组合?

在硬币图案计数问题中(给定一个值 N 和一组固定的硬币,我们必须计算加起来为 N 的硬币组合的数量。),如果我们想打印组合而不是计算组合,什么是该方法 ?我必须为此使用动态编程吗?

0 投票
8 回答
60143 浏览

algorithm - 为什么贪心硬币找零算法对某些硬币组不起作用?

我了解硬币找零问题的贪心算法(用尽可能少的硬币支付特定金额)是如何工作的——它总是选择面额最大的硬币,但不超过剩余的总和——并且它总能找到正确的解决方案特定的硬币套装。

但是对于某些硬币组,贪心算法会失败。例如,对于集合{1, 15, 25}和总和 30,贪心算法首先选择 25,余数为 5,然后是 5 个 1,总共有 6 个硬币。但是硬币数量最少的解决方案是两次选择 15。

一组硬币必须满足什么条件才能使贪心算法找到所有和的最小解?

0 投票
2 回答
5779 浏览

dynamic-programming - 硬币变化的变化

所以典型的硬币找零问题要求你弄清楚你是否可以使用无限的面额硬币 x1、x2、...、xn 来换取价值 v,但我想知道你如何才能弄清楚每个硬币最多使用一次同样的问题?

对于最初的问题,我知道您可以遍历值的前缀并查看是否可以为 v-x_i 进行更改,但是当它被限制为每个面额最多一个硬币时,我不知所措。

有什么建议可以让我开始吗?我可能在想你也可以迭代面额的前缀。虽然不确定...

0 投票
1 回答
3880 浏览

algorithm - 硬币找零算法和伪代码:需要澄清

我正在尝试了解硬币找零问题的解决方案,但遇到了一些困难。

Algorithmist中,有一个动态规划解决方案的伪代码解决方案,如下所示:

这是一个非常标准的O(n^2)算法,可以避免使用二维数组多次重新计算相同的答案。

我的问题有两个:

  1. 如何定义基本案例并将它们合并table[][]为初始值
  2. 如何从表中提取不同的序列

关于问题 1,此算法存在三种基本情况:

  • if n==0, return 1
  • if n < 0, return 0
  • if n >= 1 && m <= 0, return 0

如何将它们合并到table[][]中,我不确定。最后,我不知道如何从数组中提取解决方案集。

0 投票
3 回答
1127 浏览

c++ - 计算做出改变的方法的数量

我有一套硬币 1,2,4,10,20,40,100,200,400,1000,2000 美分。我想知道有多少种方式可以支付一定金额(<= 6000)。我目前在 c++ 中的解决方案是使用动态编程,如下所示:

但是我的输出不正确:-956301262。是因为任何溢出问题吗?

0 投票
2 回答
644 浏览

java - 无法打印出最小零钱算法中使用的面额

所以我写了一个递归算法来解决一个问题,即找出一组特定面额的“硬币”的最少数量,以达到给定的总和。该算法似乎有效,但因为它是递归的,并且在选择一个或另一个之前计算每个可能的选项,我很难想出一种方法来打印出所使用的面额。所以基本上我可以计算出可能使用的最少硬币数量,但不能计算它们是哪些硬币。这是我用来驱动它的代码和小主要方法。任何简化算法本身的建议也将受到欢迎。

0 投票
1 回答
3248 浏览

c++ - 硬币找零 C++

我试图以这样一种方式解决硬币找零问题,它会计算可以使用的最小硬币数量。我在http://www.algorithmist.com上使用了算法帖子。这是算法:

但是当我编写代码时,它会运行到无穷大。

这是代码:

有什么问题?

0 投票
1 回答
4281 浏览

c++ - 硬币变化自下而上的动态规划

http://uva.onlinejudge.org/external/6/674.html我正在尝试解决这个问题。但请注意,这不是最小硬币找零问题,它要求我使用 50、25、15、10、5 和 1 美分硬币制作 N 美分的不同数量的方法。这很简单,所以我做了这个函数:

也相当简单的是添加带有记忆的动态编程:

然而,这些都不够快——我需要自下而上的动态编程,但我在编码它时遇到了困难,即使在 Algorithmist 的帮助下——http: //www.algorithmist.com/index.php/Coin_Change

由于某种原因,每个结果我都得到 0,这是我的完整代码: