如何使用递归输出最小变化问题中的实际硬币组合

Question

给定一个硬币面额列表和一个目标值，我正在尝试创建一个递归函数，它将告诉我生成该值所需的最小硬币数量，然后显示我需要哪些硬币。例如，输入硬币[1,5,10,25]，目标为6，输出应该是“你需要2枚硬币：[1,5]”。我写了一个函数，告诉我需要多少硬币，但我也想看看硬币的组合是什么。

# USD - $1, $5, $10, etc.
currency = [1, 5, 10, 20, 50, 100]

# the amount to change - eg $6
amount = 6

cache = dict() 

def recursive_change(currency, amount):
  if amount in cache.keys() is not None:
    return cache[amount]

  # base case
  if amount == 0:
    return 0

  result = amount+1 # initially result is just some high number 
  #I figure amount + 1 is fine because we'd never use more coins than the value (assuming we can't have coins worth less than one)

  for coin in currency:
    if coin <= amount:
      result = min(result, recursive_change(currency, amount-coin) + 1)
  cache[amount]=result
  return result

这是我刚刚制作的另一个版本-我注意到我的初始解决方案不能很好地处理不可能的输入（例如，只使用五分镍币和一角镍币赚6美分），所以现在它返回-1表示不可能的数量。虽然有点难看，但我希望能为它做得更好一些。

def recursive_change(currency, amount):
  if amount in cache.keys():
    return cache[amount]

  # base case
  if amount == 0:
    return 0

  # If we can't make the amount with this coin, return -1
  if amount < 0:
    return -1

  result = -1

  for coin in currency:
    if coin <= amount:
      current_result = recursive_change(currency, amount-coin) 
      if current_result >= 0: 
        if result < 0:
          result = current_result 
        else: 
          result = min(current_result, result) 

  if result < 0:
    result = -1
  else:
    result = result + 1
  cache[amount]=result
  print(cache)
  return result

Answer 1

该解决方案使用递归找到贪婪算法失败的理想解决方案，使用缓存，因此它应该与DP迭代方法一样快，并输出实际的硬币组合。

# currency denominations
currency = [2,3,15,25]

# the amount to make change for - eg $30
amount = 30

# cache contains the best currency combos for each value: eg cache[7]=[5,1,1]
cache = dict()
def recursive_change(currency, amount):
  if amount in cache.keys():
    return []+cache[amount] # Had to do this [] thing so it passes a copy

  # base case
  if amount == 0:
    return []

  # If we can't make the amount with this coin, return -1
  if amount < 0:
    return [-1]

  best_combo = [-1]

  for coin in currency:
    current_result = recursive_change(currency, amount-coin)
    if current_result == [] or current_result[0] >= 0: 
      current_result.append(coin)  # if we picked a coin, we add it to the list
      if best_combo[0] < 0:
        best_combo = current_result 
        # if we found the first coin combo that works for the current problem, set best so we don't compare to -1 below
      else: 
        # if this isn't the first coin combo that works for the current problem, check to see if it's better than any of the other coin combos
        if len(current_result) < len(best_combo):
          best_combo = current_result

  cache[amount]=[]+best_combo # Had to do this [] thing so it passes a copy
  return best_combo

Answer 2

你的方法效率很低，尤其是对于大笔资金。你应该开始从最高面额产生总和，而不是从最低面额产生总和。以下是返回面额和硬币/钞票数量的更快更简单的版本：

currency = [1, 5, 10, 20, 50, 100]

def recursive_change(currency, amount):
    for c in reversed(currency) :
        if amount >= c :
            return [(amount // c, c),] + recursive_change( currency, amount % c )
    return []

recursive_change( currency, 6 )
>>> [(1, 5), (1, 1)]

这意味着一枚5硬币和一枚1硬币。

还有几个测试结果：

>>> recursive_change( currency, 77 )
[(1, 50), (1, 20), (1, 5), (2, 1)]
>>> recursive_change( currency, 99 )
[(1, 50), (2, 20), (1, 5), (4, 1)]