动态规划思想详解及示例实现

栏目: 编程工具 · 发布时间: 7年前

内容简介:动态规划思想详解及示例实现

本文以两个具体例子详细剖析动态规划算法设计思想,主要参考圣经《算法导论》,加上自己的一些理解,主要是附上了一些具体实现过程,所以希望能对大家有所帮助。

动态规划思想详解及示例实现

动态规划思想详解及示例实现

动态规划思想详解及示例实现

动态规划思想详解及示例实现

动态规划思想详解及示例实现

动态规划思想详解及示例实现

动态规划思想详解及示例实现

动态规划思想详解及示例实现

#_*_ 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),希望有所帮助


以上所述就是小编给大家介绍的《动态规划思想详解及示例实现》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Head First Servlets & JSP(中文版)

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(中文版)》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试