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