找零（动态编程） [英] Coin change(Dynamic programming)

问题描述

我对硬币兑换问题有一个疑问，我们不仅要打印给定硬币面额的{n，5,10,25}来兑换$ n的方式数量，还要打印方式

I have a question about the coin change problem where we not only have to print the number of ways to change $n with the given coin denominations for eg {1,5,10,25}, but also print the ways

例如，如果目标= $ 50，并且硬币是 {1,5,10,25} ，则

For example if the target = $50, and the coins are {1,5,10,25}, then the ways to actually get use the coins to get the target are

• 2×$ 25


• 1是获得硬币目标的实际方法×$ 25 + 2×$ 10 + 1×$ 5


• 等。

什么是最好的时间复杂度我们可以解决这个问题吗？
我试图修改动态编程解决方案，以解决硬币兑换问题，因为我们只需要若干种方法，而不需要实际的方法

What is the best time complexity we could get to solve this problem? I tried to modify the dynamic programming solution for the coin change problem where we only need the number of ways but not the actual ways

消除时间复杂性。
我确实使用记忆法，这样我就不必为给定的硬币和总价值再次解决相同的问题，但是我们仍然需要遍历所有解决方案并打印出来。所以时间复杂度肯定比O（ns）大，其中n是硬币数量，s是目标
它是指数的吗？任何帮助将不胜感激

I am having trouble figuring out the time complexity. I do use memorization so that I don't have to solve the same problem again for the given coin and sum value but still we need to iterate through all the solution and print them. So the time complexity is definitely more than O(ns) where n is the number of coins and s is the target Is it exponential? Any help will be much appreciated

推荐答案

打印组合

Printing Combinations

def coin_change_solutions(coins, S):
  # create an S x N table for memoization
  N = len(coins)
  sols = [[[] for n in xrange(N + 1)] for s in xrange(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

  return sols[S][N]


print coin_change_solutions([1,2], 4)
# => [[1, 1, 1, 1], [1, 1, 2], [2, 2]]

• 没有：我们不需要使用最后一个硬币进行总和。通过递归到 solution [s] [n-1] 直接找到所有硬币解决方案。我们采用所有这些硬币组合，并将它们复制到 with_last_sols 。

  • without: we don't need to use the last coin to make the sum. All the coin solutions are found directly by recursing to solution[s][n-1]. We take all those coin combinations and copy them to with_last_sols.

    with >：我们要做需要使用最后一个硬币。因此该硬币必须存在于我们的解决方案中。其余硬币可通过 sol [s-硬币[n-1]] [n] 递归地找到。阅读此条目将为我们提供剩余硬币应有的多种选择。对于每个可能的选择 sol ，我们附加最后一个硬币 coin [n-1] ：

    with: we do need to use the last coin. So that coin must be in our solution. The remaining coins are found recursively via sol[s - coins[n - 1]][n]. Reading this entry will give us many possible choices for what the remaining coins should be. For each possible choice , sol, we append the last coin, coin[n - 1]:

    # For example, suppose target is s = 4
    # We're finding solutions that use the last coin.
    # Suppose the last coin has a value of 2:
    #
    # find possible combinations that add up to 4 - 2 = 2: 
    # ===> [[1,1], [2]] 
    # then for each combination, add the last coin 
    # so that the combination adds up to 4)
    # ===> [[1,1,2], [2,2]]
    

  
  

  通过采用第一种情况和第二种情况的组合并连接两个列表，可以找到组合的最终列表。

  The final list of combinations is found by taking the combinations for the first case and the second case and concatenating the two lists.

  without_last_sols = [[1,1,1,1]]
  with_last_sols = [[1,1,2], [2,2]]
  without_last_sols + with_last_sols = [[1,1,1,1], [1,1,2], [2,2]]
  

  
  
  

  ---

  
  
  

  时间复杂度

  
  
  

  最坏的情况是，我们设置了一个硬币，其中所有硬币的数量从1到n： coins
  = [1,2,3,4，...，n] –可能的硬币总数 num个解决方案的组合等于整数分区的数量的s，p（s）。
  可以表明整数分区的数量p（s）增长 指数 。
  
  因此，个数解 = p（s）= O（2 ^ s）。任何解决方案都必须至少具有这个 ，以便它可以打印出所有这些可能的解决方案。因此，问题本质上是指数级的。

  ---

  Time Complexity

  In the worst case we have a coin set with all coins from 1 to n: coins = [1,2,3,4,...,n] – the number of possible coin sum combinations, num solutions, is equal to the number of integer partitions of s, p(s). It can be shown that the number of integer partitions, p(s) grows exponentially.
  Hence num solutions = p(s) = O(2^s). Any solution must have this at a minimum so that it can print out all these possible solutions. Hence the problem is exponential in nature.

  我们有两个循环：一个循环用于s，另一个循环用于n。
  
  对于每个s和n，我们计算 sols [s] [n] ：

  We have two loops: one loop for s and the other loop for n.
  For each s and n, we compute sols[s][n]:

  
  
  • 不使用：我们查看 sol [s-硬币[n-1]] [n] 中的O（2 ^ s）组合。对于每种组合，我们将在O（n）时间内将其复制。因此总体而言，这需要：O（n×2 ^ s）时间。
  
  
  • with ：我们查看 sol [s] [n] 。对于每个组合列表 sol ，我们在O（n）时间创建该新列表的副本，然后附加最后一个硬币。总体而言，这种情况需要O（n×2 ^ s）。
  

  • without: We look at the O(2^s) combinations in sol[s - coins[n - 1]][n]. For each combination, we copy it in O(n) time. So overall this takes: O(n×2^s) time.
  • with: We look at all O(2^s) combinations in sol[s][n]. For each combination list sol, we create copy of that new list in O(n) time and then append the last coin. Overall this case takes O(n×2^s).

  因此，时间复杂度为O（s×n）×O（n2 ^ s + n2 ^ s）= O（s× n ^ 2×2 ^ s）。

  Hence the time complexity is O(s×n)×O(n2^s + n2^s) = O(s×n^2×2^s).

  空间复杂度为O（s×n ^ 2×2 ^ s），因为我们有一个带有
  的as×n表，每个条目存储O（2 ^ s）个可能的组合（例如 [[1，1，1，1]，[1，1，2]，[2，2]] ），每个组合（例如 [1,1 ，1,1] ）占用O（n）空间。

  The space complexity is O(s×n^2×2^s) because we have a s×n table with each entry storing O(2^s) possible combinations, (e.g. [[1, 1, 1, 1], [1, 1, 2], [2, 2]]), with each combination, (e.g. [1,1,1,1]) taking O(n) space.

  这篇关于找零（动态编程）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！