用python动态编程赚钱

Question

这里有两个解决零钱问题的程序。第一种是一种递归程序，可以得到所有的组合，第二种是使用动态规划。然而，当我在做第二个问题时，我遇到了麻烦。它应该比第一个快，但我的程序会永远运行。我很确定我使用的是动态编程，但我不知道它有什么问题？在

注：Total是将要更改的货币，units是具有不同值的列表，stored是存储步骤值的字典。在

第一个：

def changeMoney(total, units):
    if ( total == 0 ): 
        return [{}]
    elif ( total < 0 ):
        return []
    else:
        n = len(units)
        ret = []
        for i in range(0,n):
            sols = changeMoney(total-units[i],units[i:n])
            for sol in sols:
                if ( units[i] in sol ):
                    sol[units[i]] += 1
                else:
                    sol[units[i]] = 1
            ret.append(sol)
        return ret
print(dpChangeMoney(300,[100,50,20,10,5,2,1],{}))

第二：

^{pr2}$

Answer 1

这里有一种更快的方法：

def dpChangeMoney(total, units, stored, min_ix=0):
    if total < 0:
        return []

    if total == 0:
        return [{}]

    if min_ix == len(units):
        return []

    key = (total, min_ix)
    if key in stored:
        return stored[key]

    sol_list = []
    u = units[min_ix]
    for c in range(total // u + 1):
        sols = dpChangeMoney(total - c*u, units, stored, min_ix + 1)
        for sol in sols:
            if c > 0:
                sol2 = sol.copy()
                sol2[u] = c
            else:
                sol2 = sol
            sol_list.append(sol2)

    stored[key] = sol_list
    return sol_list

如果按如下方式调用，它将打印指定案例的解决方案数：

^{pr2}$

结果是：

466800

在我的系统上，这只花了不到一秒钟的时间。（当然，您可以打印出实际的解决方案，但有很多！）在

要查看总共10的实际解决方案：

print(dpChangeMoney(10, [100,50,20,10,5,2,1], {}))

结果是：

[{1: 10}, {1: 8, 2: 1}, {1: 6, 2: 2}, {1: 4, 2: 3}, {1: 2, 2: 4}, {2: 5}, {1: 5, 5: 1}, {1: 3, 2: 1, 5: 1}, {1: 1, 2: 2, 5: 1}, {5: 2}, {10: 1}]

Answer 2

我只是想知道我的算法有什么问题。我会在到期日后更新一个更快的算法。谢谢你的建议和指导。E