用m币兑换n美元

2024-03-28 11:49:39 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在尝试解决以下问题:

Given a number of dollars, n, and a list of dollar values for m distinct coins, find and print the number of different ways you can make change for n dollars if each coin is available in an infinite quantity.

完整的问题陈述是here

在介绍我的解决方案之前,我应该说,我知道动态编程可能是解决这个问题的最佳方法。我提出的解决方案不使用动态编程,而且我知道它远远不是最有效的解决方案。不过,据我所知是正确的。在

问题是我的解决方案低估了改变的方法。例如,给定n = 75{25 10 11 29 49 31 33 39 12 36 40 22 21 16 37 8 18 4 27 17 26 32 6 38 2 30 34}作为硬币值,解决方案在应返回16694时返回182。不过,它似乎适用于较小的测试用例。在

def make_change(coins, n):    
    solns = 0
    num_coins = len(coins)
    for i in range(num_coins):
        solns = solns + make_change_rec(coins, n-coins[0], coins[0])

        # We've found all solutions involving coin. Remove it
        # from consideration
        coins.pop(0)

    return solns

def make_change_rec(coins, n, parent):
    # If n == 0 we've found a solution
    if n == 0:
        return 1

    solns = 0
    # For each coin
    for coin in coins:
        # If coin > n, can't make change using coin
        if coin > n or coin < parent: # coin < parent rule ensures we don't count same solution twice
            continue

        # Use the coin to make change 
        solns = solns + make_change_rec(coins, n-coin, coin)

    return solns  

有人能帮我理解我做错了什么吗?我用的是python3。在


Tags: ofinnumberformakereturnif解决方案
2条回答

我认为您只需要对coins数组进行排序。现在你的递归肯定会耗尽时间。所以我建议你使用经典的动态编程。在

def make_change(coins, n):
    dp = [1] + [0] * n
    for coin in coins:
        for i in range(coin, n + 1):
            dp[i] += dp[i - coin]
    return dp[n]

在你输入硬币之前,你需要把它们分类。如果递归对于更大的值运行缓慢(它会这样),您可以像这样添加记忆:

from functools import lru_cache

#leave your function as it is, but add this:
@lru_cache(maxsize=None)
def make_change_rec(coins, n, parent): 

相关问题 更多 >