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

栏目: 编程工具 · 发布时间: 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),希望有所帮助


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

查看所有标签

猜你喜欢:

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

精彩绝伦的CSS

精彩绝伦的CSS

[美] Eric A. Meyer / 姬光 / 人民邮电出版社 / 2012-7 / 49.00元

内容简介: 打造现代布局的专业技术 本书远非只是介绍基础知识,它不仅全面细致地讲解布局与效果,而且展望了HTML5和CSS3的未来。业内很少有人能像Eric A. Meyer一样详细阐明CSS,他在本书中深入分析了普遍适用的实用技术,讲解了如何选用正确的工具、如何通过jQuery使用CSS效果和CSS3技术。 本书主要内容如下: 显示或隐藏元素 通过XHTML为bod......一起来看看 《精彩绝伦的CSS》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

随机密码生成器
随机密码生成器

多种字符组合密码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码