Передача больших аргументов в проблеме изменения

Question

У меня проблема с алгоритмом изменения задачи. Моя функция coin_change_solutions хорошо работает с небольшими числами. Например, если мы передадим [1,10,25] как монеты, а 32 - как S (изменение, которое мы хотим получить), оно вернет [10,10,10,1,1]. Проблема возникает, когда я хочу передать большее число, поскольку я хочу работать с центами, а не с долларами, чтобы у меня была арифметика с фиксированной точкой c (это необходимо, поскольку работа с арифметикой с плавающей точкой c не будет хорошая идея позже). Поэтому, когда я передаю массив со всеми номиналами в центах [1,5,10,25,50,100,200,500,1000,2000,10000,50000] и 50000 как изменение, мой компилятор останавливается и не показывает никакого результата.

Знаете ли вы, что мне делать, чтобы алгоритм имел высокую эффективность и мог передавать все номиналы в центах?

def coin_change_solutions(coins, S):
  # create an S x N table for memoization
  N = len(coins)
  sols = [[[] for n in range(N + 1)] for s in range(S + 1)]
  for n in range(0, N + 1):
    sols[0][n].append([])

  # fill table using bottom-up dynamic programming
  for s in range(1, S+1):
    for n in range(1, N+1):
      without_last = sols[s][n - 1]
      if (coins[n - 1] <= s):
          with_last = [list(sol) + [coins[n-1]] for sol in sols[s - coins[n - 1]][n]]
      else:
          with_last = []
      sols[s][n] = without_last + with_last
  x = min(sols[S][N], key=len)


  return x

Answer 1

Не решение вашего запроса, а лучшее решение с меньшим пространством:

dp = [0] + [float('inf') for i in range(S)]
for i in range(1, S+1):
    for coin in coins:
        if i - coin >= 0:
            dp[i] = min(dp[i], dp[i-coin] + 1)
if dp[-1] == float('inf'):
    return -1
return dp[-1]

Предположим, dp[i] - это наименьшее количество монет, составляющих сумму S, тогда для каждой монеты в coins, dp[i] = min(dp[i - coin] + 1).

Сложность времени O(amount * coins.length), сложность пространства O(amount).