版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
1、背包问题的探索，1.01背包，主题：有n个物品和容量v的背包。 第I款的费用是ci，价值是wi。 解开哪个东西放进背包的话，价值的合计就会变得最大。 基本思维方法：这是最基本的背包问题，特点是每件物品只有一件，可以放也可以不放。 地址列方程式在子问题中定义了状态： fiv表示前I的物品正好放入容量v的背包中的最大价值。 其状态转移方程式中，fiv=maxfi-1v、fi-1v-ci wi这个方程式非常重要，基本上背包相关问题的方程式全部由其导出。 1.01背包说明了“在容量v的背包中放入前I个物品”的子问题，如果只考虑第I个物品的战略，就会成为只卷入前i-1个物品的问题。 如果不放入第I个项目
2、，则问题为“将前面的i-1个项目放入容量v的背包中”，如果放入成为fi-1v的第I个项目，则问题为“将前面的i-1个项目放入剩馀的容量v-ci的背包中”，此时1.01背包，注意：转换过程！ 中文：伪代码定：1.n. v=0.v Fv=max Fv、fv-ci wi； 1.01背包，时间复杂度： O(VN ) .空间复杂度： O(VN ) .优化：空间复杂度可以优化！ 啊！ 啊！ 时间的复杂度也可以进行常数的优化，并且应该是for v=V.0，2 .完整的背包，标题：中有n种物品和容量v的背包，每种物品都可以无限使用。 第I款的费用是ci，价值是wi。 了解哪些物品放在背包里，那些物品的费用总和不超过背包的容量，价值总和最大。 简单最优化：1)2个物品I，j满足ci=wj的话，去掉物品j.2 )去掉费用比v大的物品.变成0.1包.考虑到第I个物品，V/ci件最多，所以把第I个物品变成V/ci件的费用和价值不变的物品啊！ 二进制思想、伪查询密码： for i=1.N for v=0.V fv=maxfv、fv-cost weight注意：这里v的循环顺序与0.1背包的循环顺序不同！ 啊！ 啊！ 如果合理地交换v，n的循环顺序，效率好像会稍微提高一些。 2 .完整的背包，这里还可以存放在一维度阵列中。 2 .分析完整的背包，为什么假钞会成立。 第一个查询
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 湖北省黄石市十校联考2026届初中物理毕业考试模拟冲刺卷含解析
- 广东省佛山禅城区七校联考2026届中考物理四模试卷含解析
- 山东省日照市岚山区2026届中考押题物理预测卷含解析
- 河北省故城县市级名校2026届中考适应性考试物理试题含解析
- 2026届安徽省南陵县联考中考猜题物理试卷含解析
- 前置胎盘孕妇饮食指导查房
- 中医护理病历的护理目标
- 中医护理便秘调养课件
- 护理质量月护理管理
- 2026年土木营建机械操作工实操题库
- 2025年山东省济南市初二学业水平地理生物会考考试试题及答案
- 2026人教版二年级数学下册期末模拟测试卷（三套含答案）可直接打印
- 2026天津大学附属小学教师招聘8人-天津大学事业编考试参考试题及答案解析
- 2026年浙江省公开遴选公务员笔试试题及答案解析(综合类)
- （2026版）《商事调解条例》课件
- 2026年事业单位考试国内核心时事政治考点梳理（附50题）
- 2026年中考语文标点符号专项训练模拟试卷（覆盖高频考点）
- 雨课堂学堂在线学堂云《人工智能时代的创新思维（北京理工）》单元测试考核答案
- 2025年07月渤海银行2025年招考审计部团队负责人笔试历年备考题库附带答案详解试卷2套
- 2026年剧本杀主持人控场题库含答案
- T／CBDA35-2019 建筑装饰装修工程施工组织设计标准
评论
0/150
提交评论