递归的变化，使得算法 [英] Recursive change-making algorithm

问题描述

给定一个目标金额和硬币面值的名单，我的code应该找到达到目标所需的量最少的硬币。

例如：

• C（48，[1，5，10，25，50）= 6

  • 我们可以从48 3X <大骨节病> 25 + 3X <大骨节病> 1 ，所以6个硬币需

• C（48，[1，7，24，42）= 2

  • 48 = 2×<大骨节病> 24 ，所以2枚硬币就足够了

• C（35，[1，3，16，30，50）= 3

  • 我们可以从35 2X <大骨节病> 16 + 1X <大骨节病> 3 ，所以3个硬币就足够了

我做了code与循环，但如何让它递归？

  DEF C（I，硬币，cdict =无）：
    如果cdict ==无：
        cdict = {}
    如果我＆LT; = 0：
        cdict [I] = 0
        返回cdict [I]
    ELIF我在cdict：
        返回cdict [I]
    ELIF我的金币：
        cdict [I] = 1
        返回cdict [I]
    其他：
        分= 0
        在硬币CJ：
            结果= C（I  -  CJ，硬币）
            如果结果为0！
                如果分== 0或（结果+ 1） - ;分：
                    分= 1 +导致
        cdict [I] =分钟
        返回cdict [I]
 

解决方案

这是改变决策的问题。下面是标准的递归解决方案， V 是硬币的名单和 C 钱标的额：

 高清min_change（V，C）：
    高清min_coins（I，AC）：
        当交流== 0：
            返回0
        ELIF我== -1或AC＆LT; 0：
            返回浮动（INF）
        其他：
            返回分钟（min_coins第（i-1，AC），1 + min_coins（ⅰ，AC-V [I]））
    返回min_coins（LEN（V）-1，C）
 

这是一个优化的版本，使用动态规划：

 高清min_change（V，C）：
    M，N = LEN（V）+1，C + 1
    表= [[0] * n，用于中的x的xrange（米）]
    对于j中的xrange（1，n）的：
        表[0] [J] =浮动（INF）
    在的xrange I（1，米）：
        对于j中的xrange（1，n）的：
            AC =表[Ⅰ] [J  -  v [电流-1]]如果将j  -  v [电流-1]≥= 0，否则，浮法（'的inf'）
            表[I] [J] = MIN（表[I-1] [J]，1 + AC）
    返回表[M-1] [N-1]
 

两种实现将总是返回的最优解，但第二个将是大的输入快得多。注意，贪婪算法在其他的答案提示给出仅用于货币的某些组合的最佳解决方案 - 例如，它的工作原理为美国硬币

Given a target amount and a list of coin denominations, my code is supposed to find the fewest coins needed to reach the target amount.

Examples:

• C(48, [1, 5, 10, 25, 50]) = 6

  • we can make 48 from 3x25 + 3x1, so 6 coins are required

• C(48, [1, 7, 24, 42]) = 2

  • 48 = 2x24, so 2 coins are sufficient

• C(35, [1, 3, 16, 30, 50]) = 3

  • we can make 35 from 2x16 + 1x3, so 3 coins suffice

I made the code with for loops, but how do I make it recursive?

def C(i, coins, cdict = None):
    if cdict == None:
        cdict = {}
    if i <= 0:
        cdict[i] = 0
        return cdict[i]
    elif i in cdict:
        return cdict[i]
    elif i in coins:
        cdict[i] = 1
        return cdict[i]
    else:
        min = 0
        for cj in coins:
            result = C(i - cj, coins)
            if result != 0:
                if min == 0 or (result + 1) < min:
                    min = 1 + result
        cdict[i] = min
        return cdict[i]

解决方案

It's the change-making problem. Here's the standard recursive solution, V is the list of coins and C the target amount of money:

def min_change(V, C):
    def min_coins(i, aC):
        if aC == 0:
            return 0
        elif i == -1 or aC < 0:
            return float('inf')
        else:
            return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
    return min_coins(len(V)-1, C)

And this is an optimized version, using dynamic programming:

def min_change(V, C):
    m, n = len(V)+1, C+1
    table = [[0] * n for x in xrange(m)]
    for j in xrange(1, n):
        table[0][j] = float('inf')
    for i in xrange(1, m):
        for j in xrange(1, n):
            aC = table[i][j - V[i-1]] if j - V[i-1] >= 0 else float('inf')
            table[i][j] = min(table[i-1][j], 1 + aC)
    return table[m-1][n-1]

Both implementations will always return the optimal solution, but the second one will be much faster for large inputs. Notice that the greedy algorithm suggested in other answers gives an optimal solution only for certain combinations of currency - for instance, it works for the American coins.

这篇关于递归的变化，使得算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！