




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
信息工程大学算法设计与分析动态规划—0-1背包问题之问题描述和分析国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版0-1背包问题:给定n个物品和一个背包。第i件物品的重量为wi,价值为vi,背包的容量为c。问应选择哪些物品装入背包,使得背包中物品的总价值最大?限制条件:对每个物品只有两种选择,装入或不装入,物品不能分割。
与最大价值有关的因素背包容量和物品每个物品有两种方案选或不选穷举法共2n种方案
可以用动态规划求解吗?是否具有最优子结构性质背包容量c=7重量价值w1=3v1=5w2=4v2=6w3=5v3=10110最优解是(1,1,0),最大价值为11。问题:该问题的最优解是否包含子问题的最优解?问题:
背包容量c=7,物品总数n=3的0-1背包问题子问题:背包容量c或者物品总数n减少了的0-1背包问题问题:该问题的最优解是否包含子问题的最优解?子问题:c=3,n=2(1、3号物品)最优解是(1,1,0),最大价值为背包容量c=7重量价值w1=3v1=5w2=4v2=6w3=5v3=105背包容量c=310?剪切-粘贴法c=7,n=3,最优解(1,1,0)最大价值为11c=3,n=2(1、3号物品)最优解是(1,0),最大价值=5c=3,n=2(1、3号物品)最优解是(x1,x3),最大价值>5c=7,n=3,最优解(x1,1,x3)最大价值>11已知要证明假设得到比已知更好的最优解,出现矛盾单选题。0-1背包问题:物品总数n=3,背包容量c=7,物品重量分别为(3,4,5),价值分别为(5,6,10),对应的最优解为(1,1,0),以下说法正确的是:A.(1,1)是前2个物品在背包容量为7时的最优解。B.(1,0)不是后2个物品在背包容量为4时的最优解。子问题:c=7,n=2最优解是(1,1,0)背包容量c=7重量价值w1=3v1=5w2=4v2=6w3=5v3=1011
反证法:与已知矛盾,假设不成立
0-1背包问题满足最优子结构性质逻辑思维方法:从具体到一般从0-1背包问题的描述分析最优子结构,有一定难度。可结合具体实例
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025至2030年开关电木配件项目投资价值分析报告
- 尾矿库废水处理站EPC总承包项目可行性分析报告
- 推动学生身心健康与全面发展实践方案
- 高校辅导员的沟通艺术与试题及答案
- 协同工作的技巧方法试题及答案
- 大学生社交技巧应用能力测评试题及答案
- 深化农业职业经理人考试的内容理解试题及答案
- 植物保护与生态平衡的重要性试题及答案
- 普惠保险面试题及答案
- 强化粮食和重要农产品供给保障的策略与路径
- 2025年驾驶三力测试题及答案
- 【MOOC】研究生英语科技论文写作-北京科技大学 中国大学慕课MOOC答案
- 自考15040习新时代思想概论高频备考复习重点
- 心电监护操作评分标准
- GB∕T 37244-2018 质子交换膜燃料电池汽车用燃料 氢气
- JJG 700 -2016气相色谱仪检定规程-(高清现行)
- API SPEC 5DP-2020钻杆规范
- (完整版)有机太阳能电池课件2
- 电梯使用单位电梯使用和运行安全管理制度
- 新中初中课程建设汇报材料
- 莲中器乐演奏活动方案
评论
0/150
提交评论