硬币找零分析

Question

{1,3,5} 面值的硬币; 总和为11。 找出能够组成这个总和所需的最小硬币数量 （我们可以使用任意数量的每个面值的硬币）

我搜索了这个硬币问题，特别是使用动态规划方法的运行时间复杂度，但是没有在任何地方找到解释。

如何计算非动态方法的复杂度，然后将其改为动态方法？ （不是贪心）

编辑：

这里是一个实现，需要对其进行分析。

public int findCoinChange(int[] coins, int sum,int count) {

    int ret = 0, maxRet = -1;
    if(sum ==0)maxRet = count;
    else if(sum < 0)maxRet = -1;
    else{
        for(int i:coins){
            ret = findCoinChange(coins, sum - i,count+1);
            if(maxRet< 0)maxRet = ret;
            else if(ret >=0 && ret < maxRet){
                    maxRet = ret;
                }
            }
    }
    if(maxRet < 0)return -1;
    else return maxRet;
}

在我看来，这似乎是组合爆炸。然而，我不确定如何推导出此运行时间复杂度。

- arpit gautam

---

相关链接：https://dev59.com/B3I-5IYBdhLWcg3wKVE9 - jason

我认为贪心算法对于这个问题不适用。 - thefourtheye

thefourtheye - 贪心算法并不总是能给出最优解，例如：Sum=9;{1,4,5}，贪心算法会给出 {5,1,1,1,1}，而最优解是 {4,4}。 - arpit gautam

@arpitgautam 正确。这就是我的意思。如果一个程序适用于某些输入但对其他输入失败，那么它将不被视为正确的程序。所以贪心算法不起作用。你在评论中提到的例子应该写成{4, 5}。 - thefourtheye

没错，那是一个打字错误。 - arpit gautam

Answer 1

这个问题的动态规划解法显然是清晰的 O（k * n）（嵌套循环，blah blah blah），其中 k 是硬币的数量， n 是正在进行的找零金额。

我不知道您所说的非动态规划解决方案是什么意思。抱歉，您需要指定您所指的算法。 贪心算法在某些情况下失败，因此您不应该参考它。您是指线性规划解决方案吗？这是解决此问题的可怕方法，因为我们不知道复杂度是多少，而且可能使其运行任意缓慢。

我也不知道您所说的“将其更改为动态规划”。

- jason

---

你说得对，贪心和线性并不是解决问题的方法。我指的是使用递归。我们尝试通过从总和中减去一个面额来将问题缩小为子问题，然后解决子问题。如果最终得到零，我们就有了可追溯的路径，在所有解决方案之后，我们会寻找最小的解决方案。 - arpit gautam

这个问题是关于分析递归解决硬币找零问题的复杂度，而不是贪心/动态规划解决方案。 我尝试了一下 - 递归树最多有 n * k 层深度。但它有很多重复的分支。我不知道该如何继续下去。 - Raghu

@Raghu：从这个问题中，我搜索了使用动态规划方法解决硬币找零问题的运行时复杂度，但是无法在任何地方找到解释。 - jason

递归解决方案的复杂性将类似于计算斐波那契数列的递归解决方案。然而，Fib构建了一棵二叉树，复杂度很容易看出是O(2^n)，而找零问题的复杂度将取决于你所拥有的硬币面额的数量和大小，例如设D={1, 5, 12, 25}，随着N的增大，更多的面额集合将进入游戏，导致树根处的子节点数量增加。我认为，一般来说，可以安全地说O(k^n)。 - P. Hinker

对于复杂度分析而言，这个问题是整数背包问题的一个特例，它是弱 NP 难问题，并且可以在伪多项式时间内解决。 - abeagomez