硬币变化分析

{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; 
}

看起来像组合爆炸给我。不过，我不确定如何为此推导运行时复杂性。

来源

2013-06-21 arpit gautam

相关：http://stackoverflow.com/questions/1986828/coin-changing-algorithm – jason

我认为贪婪将无法解决此问题。 – thefourtheye

thefourtheye - 贪婪并不总是给出最好的解决方案，例如Sum = 9; {1,4,5}贪婪会给 - {5,1,1,1,1}最优是{4,4} –

的dynamic programming solution这个问题的显然O(k * n)（嵌套循环，等等等等等等），其中k是硬币的数目和n是变化被用于作出的金额。

我不知道你是什么意思的非动态编程解决方案。对不起，你将会指定你的意思。 greedy algorithm fails在某些情况下，所以你应该不是是指那个。你是说线性编程解决方案吗？对于这个问题来说这是一个可怕的方法，因为我们不知道复杂性是什么，并且可以让它慢慢地运行。

我也不知道你的意思是“改变它的动态之一”。

来源

2013-06-21 03:52:43 jason

你是对的，贪婪和线性不是要走的路。我指的是使用递归。我们试图通过从总和中减去一个面额然后解决子问题来将问题减少到一个子问题。如果我们在最后得到一个零点，我们有一条可追踪的路径，并且在所有解决方案之后，我们会寻找最小的路径。 –

问题是关于分析硬币变化问题的递归解决方案的复杂性。这不是关于贪婪/ dp解决方案。我给它一个镜头 - 递归树最多是'n * k'。但它有很多重复的分支。我不知道如何从那里继续。 – Raghu

@Raghu：从这个问题：“*我特别使用动态编程方法寻找运行时间复杂度，尤其是使用动态编程方法的运行时间复杂度，但无法在任何地方找到解释*” – jason

硬币变化分析

回答

相关问题