用Python展示动态规则法用以解决重叠子问题的示例( 二 ) _动态规划法

下面是运行上述代码的结果：
>>> n = 4
>>> c = 6
>>> w = [0, 2, 2, 3, 1]
>>> v = [0, 4, 5, 1, 2]
>>> memo = [[-1 for _ in range(c+1)] for _ in range(n+1)]
>>> knapsack(n, c, w, v, memo)
10
>>> memo
[[-1, -1, -1, -1, -1, -1, -1],
[-1, 0, 0, -1, -1, -1, -1],
[-1, 0, 4, 4, 4, 4, -1],
[-1, 0, 5, 5, 9, 9, -1],
[-1, 2, 5, 7, 9, 10, -1]]
【用Python展示动态规则法用以解决重叠子问题的示例】从上述结果可以看到，备忘录法的实现方式与动态规划法的实现方式很相似。不同之处在于，备忘录法采用递归搜索的方式，而动态规划法采用循环迭代的方式。备忘录法的时间复杂度为O(nc)，与动态规划法的时间复杂度相同。但是，备忘录法的空间复杂度较高，为O(nc) 。如果采用动态规划法，则可以将空间复杂度降至O(c) 。

用Python展示动态规则法用以解决重叠子问题的示例( 二 )

猜你喜欢