我正在尝试解决以下问题:
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。在
我认为您只需要对
coins
数组进行排序。现在你的递归肯定会耗尽时间。所以我建议你使用经典的动态编程。在在你输入硬币之前,你需要把它们分类。如果递归对于更大的值运行缓慢(它会这样),您可以像这样添加记忆:
相关问题 更多 >
编程相关推荐