问题标签 [coin-change]

这个问题专门针对硬币找零问题。我知道找到用于找到任何数量的零钱的最佳硬币数量的算法，我也理解它，但我不明白的是，如果你愿意找到这种解决方案的路径，我怎么能“标记”。我曾尝试使用父指针，我确信这是这样做的方法，但我根本不知道我将如何实现它。这是一个例子。示例：给定硬币面额：1、10、25 找零：30 最佳解决方案需要：3 个硬币使用的硬币：10、10、10

我不太擅长解决动态规划问题。

我正在尝试使用 java 硬币找零问题来枚举为 n 提供的所有可能的找零集。

我的逻辑如下：

我的代码：

这仅输出一组所有枚举：

输出：

问题：

我正在努力弄清楚一旦其中一个面额完成后如何移动到下一个面额......我知道你应该移动到面额数组中的下一个索引......但是那只会添加下一个硬币...... .如何让它添加下一个最大的硬币，然后递归地下降到下一个硬币......一直到所有4个硬币？

谢谢！

*编辑**

期望输出：列表列表... 27 美分：

LIST{ [1, 0, 0, 2], [0, 2, 1, 2], [0, 1, 3, 2]... etc}

找不到问题，每次我运行这段代码时，由于这条线，它会进入stackoverflow

基本上问题很容易。给定一个值 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。

我在网上看到的问题：一个卖瓜的农民有n个瓜。每个甜瓜的重量，一个整数 (lbs)，是不同的。一位顾客要求正好 m 磅未切开的瓜。现在，农民有以下问题：如果有可能满足客户，他应该尽可能高效地找到合适的瓜，否则告诉客户不可能满足他的要求。

注意：这不是作业顺便说一句，我只需要指导。

我的回答：这似乎类似于硬币找零问题（背包）和子集问题（回溯）。硬币兑换：我可以将权重放入一个集合 w = {5, 8, 3 , 2,....} 然后求解，子集问题也是如此。

所以基本上我可以使用任何一种方法来解决这个问题？

我在我的 SML 手册中看到了以下函数，该函数计算特定更改需要多少特定种类的硬币。例如change [5,2] 16 =[5,5,2,2,2]，因为有两个 5 硬币和三个 2 硬币，一个得到 16。

以下代码是一种回溯方法：

它有效，但我不明白具体如何。我知道回溯是什么，我只是不明白这个特定的功能。

到目前为止我的理解是：如果amt是 0，这意味着我们的变化是计算出来的，在最终列表中没有什么可以被 cons'd 的。

如果我们的“-list”中没有更多的硬币coin，我们需要后退一步。

这就是我迷失的地方：引发异常究竟如何帮助我们返回？

如我所见，处理程序尝试调用该change函数，但“ coins”参数不应该是nil吗？因此进入无限循环？为什么会“回去”？

最后一个条款对我来说非常明显：如果硬币价值大于剩余的找零数量，我们使用剩余的硬币来构建找零。如果它小于剩余的数量，我们将其添加到结果列表中。

我正在上一门 Python 编程课程，我一直在努力思考如何实现它。我已经编写了一些代码，并且正在尝试修复弹出的任何错误，但我感到困惑并且没有解决任何问题，这就是我求助于你们的原因。当您看到我到目前为止所写的内容时，我将不胜感激任何想法和建议。我特别难以弄清楚如何做最后一部分，我必须获得高于或低于 2 美元的价值。

我正在做这个练习：

创建一个找零游戏，让用户输入恰好赚两美元所需的硬币数量。实现一个 Python 程序，提示用户输入 5c 硬币、10c 硬币、20c 硬币、50c 硬币、1 美元硬币和 2 美元硬币的数量。如果输入的这些硬币的总价值等于两美元，那么程序应该祝贺用户赢得了比赛。否则程序应该显示一条消息，提示总数不完全是 2 美元，并显示值高于或低于 2 美元。

更新：我对最后一个函数进行了一些更改，它工作得非常好。

我需要给出尽可能少的零钱。我输入箱子的数量，每个箱子都有一些硬币（1不一定是其中的一部分）和我想测试的数量。然后我输入不同的硬币以及要测试的不同数字。

我不知道为什么我的程序不起作用。由于 1 不一定是更改的一部分，我不得不稍微调整程序。

编辑：“不工作”我的意思是它实际上没有做任何事情。它接受输入并且什么都不做。我认为它进入了一个无限循环。

尝试为一般的硬币找零问题编写 DP 解决方案，同时跟踪使用了哪些硬币。到目前为止，我一直在努力为我提供所需的最少硬币数量，但无法弄清楚如何获得使用了哪些硬币以及使用了多少次。如果使用硬币，我尝试使用值设置另一个表（布尔值），但这似乎无法正常工作。有任何想法吗？

一个集合的 Frobenius 数存在当且仅当该集合数的 gcd 为 1。给定一组最多有 10 个元素的正整数，使得所有元素的 gcd 为 1，我们如何计算该集合的 Frobenius 数?

这是原始问题的链接：https ://icpcarchive.ecs.baylor.edu/external/62/6298.pdf Sylvester 的公式可用于查找一组 2 个元素的 Frobenius 数。

例子：

给定 20 美元，我想计算用硬币兑换 20 美元的方式 = { 5$,10$, 15$} 硬币的顺序无关紧要。

解决方案在这里

解决方案说：总方式数 = 使用硬币 + 不使用硬币： total_ways = count( S, m - 1, n ) + count( S, m, nS[m-1] )

以树的形式：