Как вывести фактическую комбинацию монет в задаче минимального изменения с помощью рекурсии - PullRequest
Новая
       12

Как вывести фактическую комбинацию монет в задаче минимального изменения с помощью рекурсии

0 голосов
/ 29 октября 2019

Учитывая список номиналов монет и целевое значение, я пытаюсь создать рекурсивную функцию, которая сообщит мне наименьшее возможное количество монет, которое мне понадобится для получения этого значения, и затем покажет, какие монеты я 'буду нуждатьсянапример, введите монеты [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

Ответы [ 2 ]

0 голосов
/ 31 октября 2019

Это решение использует рекурсию, чтобы найти идеальные решения в случае сбоя жадного алгоритма, использует кэш, поэтому он должен быть примерно таким же быстрым, как итерационный подход 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
0 голосов
/ 29 октября 2019

Ваш подход очень неэффективен, особенно для больших сумм денег. Вы должны были начать генерировать суммы из самых высоких деноминаций, а не из самых низких. Вот более быстрая и простая версия, которая возвращает номинал и количество монет / банкнот: 

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.

Aеще пара результатов теста: 

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