首页 > 操作系统 >

分析动态编程，装饰器功能和经典问题（LCS，DAG，背包问题，序列比对(2)

电脑杂谈　发布时间：2020-04-25 11:08:51　来源：网络整理

然后迭代版本，用循环替换递归调用，并将list用作缓存:

# 用迭代方式解决无限制的整数背包问题
def unbound_knapsack(w, v, c):
    m = [0]
    for r in range(1, c+1):
        val = m[r-1]
        for i, wi in enumerate(w):
            if wi > r:
                continue
            val = max(val, v[i] + m(r-wi))
        m.append(val)
    return m[c]

您还可以[0] *（c +1）并分配一个列表，然后使用m [r] = val代替追加调用.

当然，我们来谈谈0-1背包的问题:

与上面的非常相似，但是它引入了一种思考和思考物体的方法. 令k个物体的最大值为m（k，r），r为剩余背包容量. 该物体很小，可以直接放在背包中.

实现如下:

# 用递归，记忆体化的方式解决0-1背包问题
def rec_knapsack(w, v, c):
    @memo
    def m(k, r):
        if k == 0 or r == 0:
            return 0
        i = k-1
        drop = m(k-1, r)
        if w[i] > r:
            return drop
        return max(drop, v[i] + m(k-1, r-w[i]))
    return m(len(w), c)

然后，当然有一个迭代的版本. 该工作方法与遍历算法有点相似. 这两个0-1背包问题的算法与其在时间上无限制的情况相同. 两者均为Θ（cn），并且属于伪多项式级别. 代码如下:

# 用迭代方法解决0-1背包问题
def knapsack(w, v, c):
    n = len(w)
    m = [[0]*(c+1) for i in range(n+1)]
    P = [[False]*(c+1) for i in range(n+1)]
    for k in range(1, n+1):
        i = k-1
        for r in range(1, c+1):
            m[k][r] = drop = m[k-1][r]
            if w[i] > r:
                continue
            keep = v[i] + m[k-1][r-w[i]]
            m[k][r] = max(drop, keep)
            P[k][r] = keep > drop
    return m, P

让我们谈谈最后一个问题. 序列二进制分割问题:

存在一个常见的动态编程问题，即以某种方式递归拆分某些序列.

0 1背包问题动态规划算法_动态规划算法背包问题_背包问题动态规划 python

对于ABCDE，我们可以将其分解为（（AB）（（CD）E））. 应用通常是:

矩阵乘法: 将矩阵序列乘以单个结果矩阵. 我们使用除法来最大程度地减少操作数. 解析上下文无关的语言. 这部分将不再详细描述. 如果不清楚，可以检查分析操作的数据. 最佳搜索树: 这是霍夫曼问题的特例，它会尽可能减少预期的遍历深度. 因为它是搜索树，所以叶节点的顺序无法更改背包问题动态规划 python，因此贪婪算法不适用. 我们仍将使用括号分隔

尽管应用程序不同，但问题的实质是相同的. 看看下面的图片:

由序列递归除法形成的最佳搜索树. 在以自身为根节点进行最佳分割之后，这些节点中的每个节点都对应于左右间隔.

我们只需要计算最佳成本. 为了获得真实的树，必须记住与子树的根节点相对应的开销是最优的.

让e（i，j）估计开销时间为[i: j]. 选择r作为根节点. 我们想要添加p [r]来找到根节点，这是预期成本. 除了根节点之外，还需要将与每个节点v对应的p [v]添加到最终计算中.

因此，计算包括递归:

e（i，j）= e（i，r）+ e（r + 1，j）+和（v在（i，j）范围内的p [v]）

然后，在最终解决方案中，我们必须遍历所有节点r才能找到最大值. 然后看一下具体的实现:

# 用于实现最优搜索树的记忆体递归函数
def rec_opt_tree(p):
    @memo
    def s(i, j):
        if i == j:
            return 0
        return s(i, j-1) + p[j-1]
    @memo
    def e(i, j):
        if i == j:
            return 0
        sub = min(e(i, r) + e(r+1, j) for r in range(i, j))
        return sub + s(i, j)
    return e(0, len(p))

该算法为三次方，时间复杂度为Θ（n³）.

迭代版本如下:

# 用迭代方式解决最优搜索树问题
from collections import defaultdict
def opt_tree(p):
    n = len(p)
    s, e = defaultdict(int), defaultdict(int)
    for k in range(1, n+1):
        for i in range(n-k+1):
            j = j + k
            s[i, j] = s[i, j-1] + p[j-1]
            e[i, j] = min(e[i, r] + e[r+1, j] for r in range(i, j))
            e[i, j] += s[i, j]
    return e[0, n]