内容简介:动态规划思想详解及示例实现
本文以两个具体例子详细剖析动态规划算法设计思想,主要参考圣经《算法导论》,加上自己的一些理解,主要是附上了一些具体实现过程,所以希望能对大家有所帮助。
#_*_ 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详解及示例
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Head First Servlets & JSP(中文版)
(美)巴萨姆、(美)塞若、(美)贝茨 / 苏钰函、林剑 / 中国电力出版社 / 2006-10 / 98.00元
《Head First Servlets·JSP》(中文版)结合SCWCD考试大纲讲述了关于如何编写servlets和JSP代码,如何使用JSP表达式语言,如何部署Web应用,如何开发定制标记,以及会话状态、包装器、过滤器、企业设计模式等方面的知识,以一种轻松、幽默而又形象的方式让你了解、掌握servlets和JSP,并将其运用到你的项目中去。《Head First Servlets·JSP》(中......一起来看看 《Head First Servlets & JSP(中文版)》 这本书的介绍吧!