温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Python中怎么实现动态规划

发布时间:2021-07-02 16:03:37 来源:亿速云 阅读:675 作者:Leah 栏目:大数据

今天就跟大家聊聊有关Python中怎么实现动态规划,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。

动态规划

动态规划的关键:在于大问题的最优解由对应的更小规模问题的最优解递推而来

针对博物馆大盗问题,将问题函数化:  m(i, w)
  • i(1<=i<=5):表示前i个宝贝

  • w(1<=w<=20):重量不超过w

  • m(i, w) :前i个宝贝总重不超过w的最大价值是多少

函数的意义:前1个宝物重量不超过w的最大价值,前2个宝物重量不超过w的最大价值……前5个宝物重量不超过w的最大价值。问题的规模逐渐增大,从最小规模一直推导到目标规模的最优解

动态规划:从最小规模最优解推导到目标规模问题的最优解

m(i, w)要得到最大价值,那它如何计算呢?

既然规模是从小到大,那么就要讨论第i个宝贝能否加入到上一个规模中

  • 若第i个宝贝太重了加不进去,则m(i, w)=m(i-1, w)

  • 若第i个宝贝可以加进去,则m(i, w)=m(i-1, w-wi)+vi

从上述两个结果中取较大的

算法设计:两重循环,i从1加到5的同时w从1加到20

过程中你会发现后面的m(i, w)可以通过前面已经计算过的结果直接得到

Python中怎么实现动态规划

Python中怎么实现动态规划

Python中怎么实现动态规划  
 

递归解法

递归的方法要显得自然通俗一点

  • 基本结束条件:宝贝为空或背包承重为

  • 递归最大的问题在于会有许多的重复,故需要记录中间结果

  • 规模减小方向:从宝物集合中逐个去掉(偷走)宝物,递归调用

Python中怎么实现动态规划

  

tuple()方法

用于将列表、区间等转换为元组

a = [1, 2]b = {'1':2, '2':3}print(tuple(a))print(tuple(b))
(1, 2)('1', '2')

看完上述内容,你们对Python中怎么实现动态规划有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注亿速云行业资讯频道,感谢大家的支持。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI