内容简介：动态规划思想详解及示例实现
本文以两个具体例子详细剖析动态规划算法设计思想，主要参考圣经《算法导论》，加上自己的一些理解，主要是附上了一些具体实现过程，所以希望能对大家有所帮助。
#_*_ coding:utf-8 _*_
import numpy as np
def MemoizedCutRodAux(p,n,r,s):
if r[n]>=0:
return r[n]
if n==0:
q=0
c=0
else:
q=-1
c=-1
for i in range(1,n+1):
if q<(p[i]+MemoizedCutRodAux(p,n-i,r,s)):
q=p[i]+MemoizedCutRodAux(p,n-i,r,s)
c=i
r[n]=q
s[n]=c
return q
def MemoizedCutRod(p,n):
r=-np.ones(n+1)
s = -np.ones(n + 1)
MemoizedCutRodAux(p,n,r,s)
return r,s
if __name__=='__main__':
p=np.array([0,1,5,8,9,10,17,17,20,24,30])
r,s=MemoizedCutRod(p, 10)
print r
print s
结果输出：
r=[ 0. 1. 5. 8. 10. 13. 17. 18. 22. 25. 30.]
s=[ 0. 1. 2. 3. 2. 2. 6. 1. 2. 3. 10.]
import numpy as np
def BottomUpCutRod(p,n):
r = -np.ones(n + 1)
s = -np.ones(n + 1)
r[0]=0
s[0]=0
q=-1
for j in range(1,n+1):
for i in range(1,j+1):
if q<(p[i]+r[j-i]):
q=p[i]+r[j-i]
s[j]=i
r[j]=q
return r,s
if __name__=='__main__':
p = np.array([0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30])
r,s= BottomUpCutRod(p,10)
print r
print s
★ 步骤三：采用自底向上迭代法计算最优解的值
import numpy as np
def MatrixChain(p):
n=p.size-1
m=np.ones((n+1,n+1))*np.inf
s = np.zeros((n+1, n+1))
for i in range(n+1):
m[i,i]=0
for lenth in range(2,n+1):
for i in range(1,n-lenth+2):
j=i+lenth-1
for k in range(i,j):
q=m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]
if q<m[i,j]:
m[i,j]=q
s[i,j]=k
return m,s
if __name__=='__main__':
p=np.array([50,10,40,30,5])
m,s=MatrixChain(p)
print m
print s
结果输出 ：
m=[[ 0. inf inf inf inf]
[ inf 0. 20000. 27000. 10500.]
[ inf inf 0. 12000. 8000.]
[ inf inf inf 0. 6000.]
[ inf inf inf inf 0.]]
s=[[ 0. 0. 0. 0. 0.]
[ 0. 0. 1. 1. 1.]
[ 0. 0. 0. 2. 2.]
[ 0. 0. 0. 0. 3.]
[ 0. 0. 0. 0. 0.]]
----------------------------------------------------------------------------------------------
本文为作者原创，其中代码都是可以运行通过(Python)，希望有所帮助
以上所述就是小编给大家介绍的《动态规划思想详解及示例实现》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- Laravel多用户认证系统示例详解
- Linux tcpdump 命令详解与示例
- CSS3中Transition属性详解以及示例分享
- redis实现加锁的几种方法示例详解
- bootstrap-select 的多选+模糊查询下拉框详解（官方示例文档解读）
- Python3中一些高阶函数map、reduce、filter详解及示例
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
