8wDlpd.png
8wDFp9.png
8wDEOx.png
8wDMfH.png
8wDKte.png

Python 硬币变化动态规划

Billy Groble 1月前

19 0

我目前正在尝试在 Python 中实现动态规划,但我不知道如何设置回溯部分以使其不重复排列。例如,输入将是 (6,...

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

    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
帖子版权声明 1、本帖标题:Python 硬币变化动态规划
    本站网址:http://xjnalaquan.com/
2、本网站的资源部分来源于网络,如有侵权,请联系站长进行删除处理。
3、会员发帖仅代表会员个人观点,并不代表本站赞同其观点和对其真实性负责。
4、本站一律禁止以任何方式发布或转载任何违法的相关信息,访客发现请向站长举报
5、站长邮箱:yeweds@126.com 除非注明,本帖由Billy Groble在本站《algorithm》版块原创发布, 转载请注明出处!
最新回复 (0)
  • 避免排列的方法之一是使用“非递减”顺序的数字。这样做的话,您将永远不会添加 [5 1] 的答案,因为它不是“非递减”顺序。而 [1 5] 将被添加,因为它是“非递减”顺序。

    因此,如果您修复使用排序顺序中的第 i 个数字,那么您的代码中的变化将是永远不会使用严格低于此数字的数字。

    Suparshva 的 中所述, 并对初始数字列表进行排序。

返回
作者最近主题: