下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第 PAGE4 页 共 NUMPAGES4 页Python 01背包、动态规划 Python 0/1 背包、动态规划 参考:fcyworld/p/6243012 Python 0/1 背包、动态规划 0/1 背包问题:在能承受一定重量的背包中,放入重量不同,价值不同的几件物品,怎样放能让背包中物品的价值最大? 比方,有三件物品重量 w,价值 v 分别是 w=5,3,2 v=9,7,8 包的容量是 5,也就是我们要求得 ma_Val=v1+v2+v3约束条件为:ws=w1+w2+w3我们的思路是,列举出所有可能的放入背包的选项,然后比拟哪个价值大,这需要用到决策树。决策树的思想是,用一组向量来描
2、绘当前的状态,比方 当前考虑的物品 i, 当前背包的空间 w, 当前已获得的价值 v, 决策树左儿子表示不选取当前物品 np,右儿子表示选取当前物品 p,首先递归到索引为最后一个的物品,然后回溯,每回溯到一个物品时候就比拟选取当前物品和不选取当前物品哪个更有价值1 def ma_Val(w, v, i, ws):2if i = 0:3if wi ws:9return without_i10else:11with_i = ma_Val(w, v, i-1, ws-wi) + vi#算出选取当前物品时候的价值12return ma_(without_i, with_i)131415 w = 5,
3、3, 216 v = 9, 7, 817 val = ma_Val(w, v, 2, 5)18 print(val)这个方法可以正确运行,但是为 O(2n),所以当数据量增大时候,耗时会急剧增大,有什么方法可以减小耗时?同时列举出所有可能得出结论? 这就用到动态规划了 拿上面这个例子来说 当我们考虑第二个也就是最后一个物品的时候,我们需要把第 0 个,第 1 个物品要不要选取考虑一次 当我们考虑第一个儿子时候,也要把第零个物品要不要选取考虑一次 。当物品非常多的时候,就造成了非常大的浪费 那么,我们能不能每次考虑一个物品之后,就把每种情况下的特征和值记录下来,以供以后考虑别的物品时候使用? 这
4、就是动态规划 在这个背包问题中,我们可以使用(i,ws)来描绘决策树中每种情况,同时保存对应的值。memo=def ma_Val(w, v, i, ws):# i 是序号,ws 是容量,w 是空间 v 是价值#i 需要从 w 长度减一开场,就是从大往小遍历,否那么有问题try:return memo(i,ws)e_cept KeyError:if i = 0:if wi ws:memo(i, ws) = without_ireturn without_ielse:with_i = ma_Val(w, v, i-1, ws-wi) + vires = ma_(without_i, with_i)memo(i, ws) = resre
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 趣味运动会开幕词(15篇)
- 讲文明国旗下讲话稿(3篇)
- 教师参加党代会的发言稿
- 2024版2024离婚协议书谈话笔录五篇范文
- 内墙腻子工程施工劳务合同
- c语言课程设计餐馆
- 2024年春季开学“安全教育周”活动方案
- 广州华南植物园课程设计
- 造价概算咨询服务合同
- 广东省潮州湘桥区六校联考2024届中考试题猜想数学试卷含解析
- 幼儿园公开课:大班语言《相反国》课件(优化版)
- 小学六年级数学计算题100道(含答案)
- 土建工程常见质量缺陷与处理措施方案
- lxh汽轮机TSIe
- 小学三年级上册品德道德与法治-《走近我们的老师》(23张)ppt课件
- 最新 育婴师实操技能题
- 劳务培训计划
- 项目部管理人员分工
- (完整版)钢板焊接施工方案
- (完整版)生产异常问题反馈流程
- 航车安全操作规程
评论
0/150
提交评论