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

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


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

查看所有标签

猜你喜欢:

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

Beginning Google Maps API 3

Beginning Google Maps API 3

Gabriel Svennerberg / Apress / 2010-07-27 / $39.99

This book is about the next generation of the Google Maps API. It will provide the reader with the skills and knowledge necessary to incorporate Google Maps v3 on web pages in both desktop and mobile ......一起来看看 《Beginning Google Maps API 3》 这本书的介绍吧!

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

在线图片转Base64编码工具

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

UNIX 时间戳转换

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具