问题标签 [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 投票
2 回答
4743 浏览

c# - C# 中的硬币兑换,硬币数量有限

我构建了以下完美运行的硬币变化(C#):

我的问题是我不知道如何限制每枚硬币的硬币数量。例如,我想要最多 4 个 500 欧元的硬币、6 个 10 欧元的硬币、5 个 2 欧元的硬币等。硬币找零会返回每个硬币使用的硬币数量,这真是太棒了.

你能帮我吗?谢谢你。

0 投票
1 回答
491 浏览

java - 为什么面额数组的排序在硬币兑换中很重要

请在下面的链接中查看最小硬币变化问题的解决方案

http://techieme.in/minimum-number-of-coins/

在这里,作者假设

面额数组按升序排列。

我的问题是为什么面额数组的排序很重要。

下面的链接也采用了类似的假设 (请注意,这里作者正在解决可以进行硬币更换的不同方式,而不是最小硬币更换)

http://www.algorithmist.com/index.php/Coin_Change

现在有了 S1 < S2 < ... < S(M) 的限制,我们的解决方案可以按非递减顺序构建

所以假设如果我的面额数组是无序的,我会得到错误的硬币兑换方式吗?

0 投票
1 回答
2239 浏览

prolog - 序言:硬币变化

我是 prolog 的新手,试图解决这个经典的硬币找零问题。

change(M,P,N,D) 用 M>=0 和 M = P+5*N+10*D 的公式这是我的方法

几个测试用例

但是,如果我尝试

它给了我“参数没有充分实例化”而不是 P = 10。这是什么原因?

编辑:通过使用介于(0,M,P),介于(0,M,N),介于(0,M,D)之间,M是P + 5 * N + 10 * D之间的谓词来修复我的代码。

0 投票
2 回答
1057 浏览

c++ - 硬币找零问题

假设我有 4 个面额为 1 3 4 5 的硬币。我想把它变成 7。我学习如何找到可以完成的可能方法。但我想确定为此必须使用的最少硬币数量是多少。示例:5+1+1=7 再次 3+4=7。所以硬币的最小数量是2。任何伪代码或解释或源代码都会有所帮助

0 投票
1 回答
649 浏览

python - 记忆:用硬币找零

我正在用 Python 解决经典的硬币问题。这是我的实现。

事实证明,memoized 版本比原始版本还要慢!为什么?我的实施出了什么问题?

这是没有记忆的:

这是记忆:

0 投票
1 回答
236 浏览

algorithm - 最小硬币变化变化

Min-Coin Change 问题已得到充分研究(可以在此处找到解释:http ://www.algorithmist.com/index.php/Min-Coin_Change ),但我有兴趣解决它的变体:

对于一组值 V,确定最小的硬币集 C,使得 V 中的每个值都可以作为 C 中的硬币的总和获得,其中该组中的每个硬币最多只能使用一次。最小是指最少的硬币数量。

例如,如果 V = {3, 8, 9, 10, 11} 那么很容易看出 C = {1, 2, 8} 因为 1 + 2 = 3, 8 = 8, 9 = 1 + 8, 10 = 2 + 8 和 11 = 1 + 2 + 8。没有更小的集合 C' 也涵盖所有这些数量。

到目前为止,我想不出比暴力破解子集更好的工作方法,这显然不适用于大 V。我正在寻找有人向我展示更好的解决方案或为我指出相关问题的方向。

编辑:请注意,可能有多个最小集,我有兴趣只找到其中​​一个。

0 投票
1 回答
1318 浏览

dynamic - 无界背包/硬币找零,非标硬币最优解

我有以下问题:

给定目标大小 N 和存储在数组 denominations[] 中的一些随机生成的硬币的一些面额,使用动态编程检查是否存在最佳解决方案,该解决方案将用最少的硬币数量填充整个目标。

这是硬币找零问题的典型示例,但与现实生活中的货币不同,每种面额都经过仔细挑选,以便可以匹配任何目标,但情况并非如此。

我熟悉硬币找零问题中使用的算法以及如何构造动态编程数组来找到解决方案,但是我如何首先检查是否有解决方案?

0 投票
1 回答
164 浏览

c++ - 迭代方法似乎比递归实现(硬币变化)慢

来自uva OJ的问题

我的递归解决方案

这个被接受了(并花了 0.024 秒)

我的迭代方法:

但是我超过了这个时间限制。它给出了正确的输出,但我看不出这个必须这么慢的原因?

0 投票
2 回答
502 浏览

arrays - 为什么我在硬币变化动态编程方法中得到一个错误的测试用例?

我正在尝试使用动态编程方法解决硬币找零问题。我所做的是使用了占用空间较小的一个。这是我的代码:

它显示以下测试用例的错误答案:输入:250 24 41 34 46 9 37 32 42 21 7 13 1 24 3 43 2 23 8 45 19 30 29 18 35 11 预期输出:15685693751

0 投票
3 回答
3216 浏览

c - C程序用while循环计数硬币

我见过很多人提到过这个特定的 C 程序,尽管形式不同。但是,我似乎无法确定问题的根源,也无法找到其他有帮助的答案。程序编译,甚至执行正确,除了一个单一的输入:4.2

该程序似乎计算了将零钱输入为输入所需的最小硬币数量,4.2 除外。它输出 22 而不是应有的 18(16 个季度,2 个角钱)。有什么想法吗?我正在审核一门在线课程,没有学分/没有学术不诚实问题。