我正在尝试针对以下问题实现解决方案:
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
有人可以帮助我理解我做错了什么吗？我正在使用 Python 3。
最佳答案
我认为您需要做的唯一更改是对 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]
关于python - 用 m 个硬币找 n 美元，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47258358/