问题标签 [coin-change]

我一直在使用动态编程解决硬币找零问题。我试图创建一个数组 fin[] ，其中包含该索引所需的最小硬币数量，然后打印它。我写了一个我认为应该给出正确输出的代码，但我不知道为什么它没有给出准确的答案。例如：对于输入：4 3 1 2 3 （4 是改变的数量，3 是可用硬币类型的数量，1 2 3 是硬币值的列表） 输出应该是：0 1 1 1 2（因为我们有 1,2,3 作为可用硬币，它需要 0 个硬币来改变 0，1 个硬币来改变 1，1 个硬币来改变 2，1 个硬币来改变 3 和 2 个硬币来改变 4) 但它给出 0 1 2 2 2

这是代码：

我参考了这个页面：http: //interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html

任何人都可以帮忙吗？

我试图解决这个问题，给定一定面额的硬币，我想找到最大数量的硬币来找零。

示例假设我得到了价值 3 和 5 的硬币，我想找 15 的硬币，解决方案是 {3,3,3,3,3}（感谢 JoSSte 指出）同样，假设价值 3 和 5 的硬币，我想找 7 的硬币，我需要显示“No solution possible”

我能够做到这一点以找到最少的硬币数量，如下所示

请注意，我有一个名为 if(n<0) 的检查，其中不加总和的组合通过将它们的大小设置为不能是最小值的非常大的数字从选项中删除。

但是，我怎样才能修改上面找到最大的硬币数量

我有一个list不同的正整数数组，代表一个集合L和一个整数S。L计算其元素之和等于 的所有子集的最快方法是什么S，而不是遍历所有子集并仅检查每个子集的和是否等于S？

我正在尝试使用递归来找到最小数量的硬币来达到给定的数量。我的代码能够列出所需的最少硬币数量，但我似乎找不到打印出用于提出解决方案的硬币的方法。我已经搜索并找到了类似的示例，但我似乎无法正确地将其应用于此。

到目前为止，这是我所拥有的：

到目前为止运行的代码示例：

如果有人能给我一些关于如何做到这一点的见解，将不胜感激。

周围有很多硬币找零问题和答案，但我找不到这个，我想知道它是否甚至是硬币找零问题。

基本上我有一堆不同的硬币，每个硬币的数量都是无限的。

所以说有成堆的各种面额。每个堆栈都是无限的。（所以无限数量的 25c 硬币，无限数量的 2c 硬币等）。

然而，在每叠硬币的顶部是一个特殊硬币，其价值大于（或等于）下面的硬币。如果不在上面使用此硬币，我将无法访问下面的硬币。

我正在努力解决的是赚取一定金额所需的最少硬币数量。

我认为这是可解决的动态编程，但我不确定如何将此限制添加到传统解决方案中。

我想知道是否应该在我使用它后将其删除并用普通硬币替换它，但我似乎无法推断这是否会破坏算法。

下面的问题是在比赛中（现在已经结束）比赛链接。

它似乎是经典硬币面额问题的变体 - 给定一个具有硬币值和数字 n 的数组（k 个元素）。我们需要回答可以计算 n 面额的方法的数量。我们可以解决它，DP这需要O(n*k)时间。现在在比赛问题中，不是给出硬币值数组，而是有一个值 m，并且硬币值都是 m ex 的所有可能幂。n= 200, m=3.所以我们有硬币价值[3^0, 3^1, 3^2, 3^3, 3^4]，更高的权力对这个例子没有用]。

我DP在这里使用了方法，但它的给予TLE。通过查看时间限制testcases<=10000, n<=10000, m<=10000，我假设我们必须在给定n,m的O(n)时间内解决它[可能还需要优化这个。请帮我解决这个问题。我的解决方案使用DP.

经典的硬币找零问题在这里得到了很好的描述：http ://www.algorithmist.com/index.php/Coin_Change

在这里，我不仅要知道有多少组合，还要打印出所有的组合。在我的实现中，我在该链接中使用了相同的 DP 算法，但我没有记录 DP 表中有多少组合，DP[i][j] = count而是将组合存储在表中。所以我在这个 DP 表中使用了 3D 矢量。

我试图改进我的实现，注意到在查找表时，只需要最后一行的信息，所以我并不需要总是存储整个表。

但是我改进的 DP 解决方案似乎仍然很慢，所以我想知道下面的实现中是否存在一些问题，或者可以进行更多优化。谢谢！

可以直接运行代码：

编辑：仍在努力，虽然取得了进展。

快速概述：这个硬币找零算法应该接收可能的找零选项和投标列表。它应该递归地输出一个镜像数组和进行招标所需的硬币数量，我认为最好的方法是使用元组。

例如：

> recursion_change([1, 2, 5, 10, 25], 49)

>> ([0, 2, 0, 2, 1], 5)

工作代码示例：

http://ideone.com/mmtuMr

特别是，这一行：

1 + _helper_recursion_change(i, k-coins[i], change_list))

正如程序现在所做的那样，捕获我们需要的硬币数量很容易。我是否必须更改返回值以包含 change_list，以便我可以增加它？在不弄乱递归的情况下最好的方法是什么，因为它目前只返回一个简单的整数。

用 change_list[i] + 1 替换上面列表中的 change_list 会给我 a TypeError: 'int' object is unsubscriptableor change_list[i] += 1 运行失败，因为它是“无效语法”。

我有无限的 4 种硬币类型：[1, 5, 25, 50]。如何挑选准确的 48 枚硬币来准确地找 1 美元？（以任何一种有效方式）

我知道如何递归地解决这个问题，但是可以使用 DP 解决它吗？如何？谢谢！

我正在尝试实施硬币兑换问题，该问题指出

硬币兑换问题被描述为给定一个值 N，如果我们想用 N 美分找零，并且我们有无限供应 S = {S1, S2, . . . , Sm} 值钱的硬币，有多少种方法可以找零？硬币的顺序无关紧要。用贪心法确定所有可能改变 N 分的方法。例如，对于 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。

注意：这不是原始的硬币更换问题，我们必须找到最佳解决方案（即最小硬币数量）

在我下面的 python 实现中，我使用了一个名为 $check$ 的列表名称。问题是程序在整个运行期间都使用相同的 $check$ 列表，因此我得到了错误的结果。它应该使用它的函数调用本地的 $check$ 列表。任何人都可以找到解决这个问题的方法吗..