算法导论:钢条切割

dbhllnr 2020-07-04

《算法导论》第十五章 动态规划首先讨论了钢条切割问题,下面做个简单的总结:

一、递归

# 价格数组
Ap=[0,1,5,8,9,10,17,17,20,24,30]
def cutrod(n):
    if n==0:
        return 0
    m = -1
    for i in range(1,n+1):
        t = cutrod(n-i)
        r = Ap[i] + t
        m = max(m,r)
    return m

从函数执行角度看,这个递归过程是一个纯函数,未产生任何副作用,从而影响到函数调用栈的上一层。

从问题角度看,则是拆解后的子问题,不依赖以任何原问题的信息。

二、动态规划(记忆数组)

# 收益
Mr = {}
# 第一段切割长度
Ms = {}
def cutrod_memo(n):
    if n==0:
        return 0
    if n in Mr.keys():
        return Mr[n]
    m = -1
    s = -1
    for i in range(1,n+1):
        t = cutrod_memo(n-i)
        r = Ap[i] + t
        if r>m:
            m = r
            s = i
    if n not in Mr.keys():
        Mr[n]=m
        Ms[n]=s
    return m

def main():
    l = 9
    r1 = cutrod(l)
    print("最大收益: ")
    print(r1)
    r2 =  cutrod_memo(l)
    print("最大收益: ")
    print(r2)
    print("收益:")
    print(Mr)
    print("第一段的切割长度: ")
    print(Ms)


if __name__ == "__main__":
    main()

递归过程中实际上创建了一颗递归调用树,通过存储子问题的答案,避免重复求解相同的子问题的答案。随后如果出现相同的子问题,则通过检索获取答案。从而将一个指数时间的求解过程,转化为多项式时间的查表过程。

相关推荐