Python硬币更改动态编程 [英] Python Coin Change Dynamic Programming

问题描述

我目前正在尝试在Python中实现动态编程，但是我不知道如何设置回溯部分，以使其不会重复排列。
例如，输入为（6，[1,5]），预期输出应为2，因为有2种可能的方式来排列1和5，以使它们的总和等于6。这些组合是{1,1,1,1,1,1}和{1,5}，但是我的程序当前工作的方式，它说明了上面显示的组合和组合{5,1}。这导致输出为3，这不是我想要的。所以我的问题是如何防止重复排列？。我的当前代码如下所示。

 导入集合为c 
 
类DynamicProgram（object）：
 def __init __（self）：
 self.fib_memo = {} 
＃嵌套字典，collections.defaultdict比常规嵌套字典更好。
 self.coin_change_memo = c.defaultdict（dict ）
 self .__ dict __。update（{x：k for x，k in locals（）。items（）if x！='self'}）
 def coin_change（self，n，coin_array）： 
＃检查缓存
如果self.coin_change_memo中为n：
如果self.coin_change_memo中的len（coin_array）[n]：
 return [n] [len（coin_array）] 
 
＃基本情况
如果n< 0：返回0 
 elif n == 1或n == 0：返回1 
 
结果= 0 
i = 0 
 
＃回溯（此函数如何工作的主干）
而i< = n和i< len（coin_array）：
结果+ = self.coin_change（n-coin_array [i]，coin_array）
i + = 1 
 
＃追加到缓存
 self中。 coin_change_memo [n] [len（coin_array）] =结果
 
＃返回结果
返回结果
  

解决方案

避免排列的一种方法是按非递减顺序使用数字。这样，您将永远不会为[5 1]添加答案，因为它不是按非递减顺序排列的。而[1 5]也将按非递减顺序添加。

因此，代码中的变化将是，如果您确定要按排序顺序使用第i个数字，则永远不会使用严格低于此数字的数字。

代码更改将按照 Suparshva的答案进行，其中包含初始编号列表。 / p>

I am currently trying to implement dynamic programming in Python, but I don't know how to setup the backtracking portion so that it does not repeat permutations. For example, an input would be (6, [1,5]) and the expected output should be 2 because there are 2 possible ways to arrange 1 and 5 so that their sum is equivalent to 6. Those combinations are {1,1,1,1,1,1} and {1,5} but the way my program currently works, it accounts for the combinations displayed above and the combination {5,1}. This causes the output to be 3 which is not what I wanted. So my question is "How do I prevent from repeating permutations?". My current code is shown below.

    import collections as c

    class DynamicProgram(object):
        def __init__(self):
            self.fib_memo = {}
            # nested dictionary, collections.defaultdict works better than a regular nested dictionary
            self.coin_change_memo = c.defaultdict(dict)
            self.__dict__.update({x:k for x, k in locals().items() if x != 'self'})
        def coin_change(self, n, coin_array):
            # check cache
            if n in self.coin_change_memo:
                if len(coin_array) in self.coin_change_memo[n]:
            return [n][len(coin_array)]

            # base cases
            if n < 0: return 0
            elif n == 1 or n == 0: return 1

            result = 0
            i = 0

            # backtracking (the backbone of how this function works)
            while i <= n and i < len(coin_array):
                result += self.coin_change(n-coin_array[i], coin_array)
                i += 1

            # append to cache
            self.coin_change_memo[n][len(coin_array)] = result

            # return result
            return result

解决方案

One of the way of avoiding permutation is to use the numbers in "non-decreasing" order. By doing so you will never add answer for [5 1] because it is not in "non-decreasing" order.And [1 5] will be added as it is in "non-decreasing" order.

So the change in your code will be if you fix to use the ith number in sorted order than you will never ever use the number which is strictly lower than this.

The code change will be as described in Suparshva's answer with initial list of numbers sorted.

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