问题标签 [coin-change]

uva 166 - dp 问题在这里

因此，如果我们需要支付 55c，而我们没有持有 50c 的硬币，我们可以按 2*20c + 10c + 5c 支付，总共 4 个硬币。如果我们出价 1 美元，我们将收到 45c 的找零，这也涉及 4 个硬币，但如果我们出价 1.05 美元（1 美元 + 5c），我们会得到 50c 的找零，而易手的硬币总数只有 3 个。

我不是在寻求解决方案，我不明白这个例子在说什么：

所以，我们需要支付 55c ，硬币 = {5,10,20} ，55c = 2*2 + 1*10 + 1*5 - 4 个硬币。

但下一步是什么？“如果我们投标 1$，我们将收到 45c？这是什么意思？1 - 45 = 55？是的，这很明显，但问题只是问如何更改 55C？

最后一个是1.05？但是对于 1.05 案例 - 他们不知道有哪些硬币可用！完全混乱

有人可以提供更多细节吗？我不明白这个问题和例子！

一旦机器接管，每枚硬币的面额将是 2 的幂：1 美分、2 美分、4 美分、8 美分、16 美分等。硬币的数量没有限制可以是值得的。

如果硬币的价值之和为n，则一组硬币改变n。例如，以下集合对 7 进行更改：

7 1 美分硬币 5 1 美分，1 2 美分硬币 3 1 美分，2 2 美分硬币 3 1 美分，1 4 美分硬币 1 1 美分，3 2 美分硬币 1 1 美分， 1 2 美分，1 4 美分硬币因此，有 6 种方法可以为 7 找零。

编写一个函数 count_change，它接受一个正整数 n，并返回使用这些未来硬币为 n 找零的方法数。

我一直在研究这个问题一个小时，试图使用树递归，但它不起作用。我正在考虑使用当前金额的 2 个分支 - 1 和当前金额 - 可能的最大硬币价值，但结果永远无法满足。

请给我一个如何处理它的建议......谢谢！

我是 Prolog 的新手，我想编写一个函数，它返回所有不同的方式来换一美元（100 美分）。我们有 2 美分硬币、11 美分硬币、38 美分硬币，有趣的是，还有 -8 美分硬币（价值 -8 美分的硬币）。此外，我们总共只有 10 枚“-8”美分硬币。（其他种类的硬币没有上限）

这是我的尝试：

但它不起作用。当我运行它并查询时

我收到消息

为什么是这样？我该如何解决？

原始问题陈述：

硬币有 4 种：2 美分、11 美分、38 美分，有趣的是，-8 美分（价值-8 美分的硬币）。更有趣的是，总共只制作了 10 -8 美分的作品，因此您无需担心超过 10 -8 美分的情况。

一美元（100 美分）有多少种不同的方法？

例如，为 100 美分找零的一种方法是使用 4 个 2 美分、8 个 11 美分、2 个 38 美分和 9 个 -8 美分。

有可能有 0 个硬币，例如 50 个 2 美分硬币是为一美元找零的一种方法。

编写一个名为 change100(Coins) 的 Prolog 函数，其开头如下：

P2 是 2 美分硬币的数量，P11 是 11 美分硬币的数量，依此类推。请记住，如问题描述中所述，Pn8 最多为 10。

我编写程序来改变硬币。当我在循环中编写 printf 以打印 i 或 j 程序时会产生良好的结果，当我删除它时，程序会停止。我认为这是内存问题，但我在 QT 中的 Windows 上编写，我无法访问 valgrind。

任何人都可以检查这个？首先给出面额的数字，第二个是面额，最后是数量。

例如：

结果应该是2。

结果应该是NO。

我正在尝试解决硬币找零问题：

给定一个数字 k 的列表，有多少种方法可以改变给定的数量 m。

作为资源之一，我有以下伪代码：

但是我不明白这个伪代码。当它们应该在后面时，它在前面有算术符号。我了解 else 语句开始的地方。但是当进入 else 循环时，我不知道发生了什么。您能否将此伪代码简化为在 else 子句之后的每个步骤中要做的一些逻辑事情？

或者有什么文章比这个伪代码解决这个问题更有用。谷歌搜索这个我只发现要求你给出最佳改变的问题，但我不需要那个。

注意请不要给我代码，因为这是一个 coursera 课程，直接回答会违反荣誉代码。

更新 正如@EmilVikström 亲切地向我解释了那里到底发生了什么，我试图生成一个应该与方案相同的小伪代码（这只是 else 子句，因为其余的甚至是不言自明的我）。

这是计划的结果吗？如果不是我哪里出错了？请再次不要给我答案（如果可以的话，请指出我正确的方向），因为这将违反 coursera 荣誉守则。

我编写的代码使用动态编程解决了基本的硬币找零问题，并给出了找零所需的最小硬币数量。但是我想将每个硬币的数量存储在最小数量中。

我正在尝试做的是初始化一个数组count[]，就像散列一样，它会增加找到的次数coin[j]，min即count[coin[j]]++. 但这不是我想要的方式，因为它每次找到min对应于时都会添加硬币coin[j]。因此，该数字不是最终答案中硬币的最终计数。

这是代码：

硬币找零是一个非常流行的问题，它询问有多少种方法可以使用硬币（C[0]、C[1]...C[K-1]）得到 N 美分的总和。DP的解决方法是使用s(N, K) = s(N, K-1) + s(NC[K-1], K)的方法，其中s(N,K)是到达的路数与前 K 个硬币的总和为 N（按升序排序）。这意味着使用前 K 个硬币赚取 N 美分的方法的数量是在不使用第 K 个硬币的情况下达到相同总和的方法数量加上获得 N-第 K 个硬币的方法数量的总和。我真的不明白你怎么会遇到这个解决方案，以及它在逻辑上的意义。有人可以解释一下吗？

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

我写了下面的代码，但它总是返回比实际答案少一个。我想知道这是否是编写解决方案的正确方法？

I am constructing a bottom-up approach to the coin change problem. I have to give the minimum number of coins needed to give the change requested. It may be possible that the change could not be given because the given denominations cannot form the value.

For example, it the given denominations are {4, 8} and they ask for a change of 5 then it is impossible to give 5. I constructed the program below and it works well for most situations unless it is impossible to form the requested change. For example, when the denominations is just {4} and I request 5, it returns one which is false. What can I do to correct this problem?

Here P represents the change requested, S are the number of denominations stored in the array denominations[] from index 0 to S - 1. dp is a two dimensional array for calculation initialized to -1.

Thank you for your help.

如何将一定数量的钱兑换成纸币和硬币？假设输入是 1234,26，我们有 1000、500、200、100、50 的纸币和 20、10、1 和 0.5 的硬币？因此，如果输入大于 .25 且小于 0.75，则应四舍五入为 1x 0.5，如果其介于 0.75 和 1.00 之间，则应四舍五入为 1x 1，如果小于 0.25，则应四舍五入为空？这个确切的程序所需的输出看起来像这样：

如果不是 0.5 硬币，我想我可以使用 int 和 % 来做到这一点，但到目前为止我几乎一无所知（认为我必须使用数组，但我不确定如何使用）并且没有想法如何开始。我也是初学者，如果您在回答和解释时也能记住这一点！任何提示/解决方案？提前致谢！

像这样？：

仍然不确定如何处理 0.5，因为我必须使用 int，只输入因为如果我使用 double 我完全错了，我还必须对 0.5 硬币使用 if 语句..