时间戳

首页 > 解决方案 > 在变革问题中传递大论据

python - 在变革问题中传递大论据

问题描述

我对变革问题算法有疑问。
我的函数 coin_change_solutions 适用于小数字。例如，如果我们将 [1,10,25] 作为硬币传递，将 32 作为 S（我们想要获得的零钱）传递，它将返回 [10,10,10,1,1]。当我想传递更大的数字时会出现问题，因为我想对美分而不是美元进行运算，这样我就有了定点算术（这是必须的，因为以后对浮点算术进行操作不是一个好主意）。
因此，当我传递一个以美分 [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

标签： pythonpython-3.xalgorithmdynamic-programming

解决方案

不是您查询的解决方案，而是空间更少的更好解决方案：

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

推荐阅读