时间戳

首页 > 解决方案 > 如何使用递归在最小零钱问题中输出实际的硬币组合

python - 如何使用递归在最小零钱问题中输出实际的硬币组合

问题描述

给定硬币面额和目标值的列表，我正在尝试创建一个递归函数，该函数将告诉我产生该值所需的最小硬币数量，然后显示我需要哪些硬币。例如输入硬币 [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

标签： pythonrecursion

解决方案

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

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)]

推荐阅读