版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025-2030中国塑代木市场应用状况与供应情况预测报告
- 幼年粒单核细胞白血病总结2026
- 大班综合有趣的年俗
- 就业指导课程体系建设
- 社区防汛应急处置
- 口腔运营渠道策划方案范文相关7篇
- 服装人职业规划：从设计到管理
- 2026年国家公务员行测真题卷
- 2025年广西壮族自治区南宁市初二学业水平地生会考考试题库（附含答案）
- 2025年广西壮族自治区防城港市八年级地生会考试题题库(答案+解析)
- ESG基础知识培训课件
- 法律效应的婚内保证书
- 育肥猪场月度汇报
- 多重耐药感染临床案例深度剖析
- 北京大学2022年强基计划笔试数学试题（解析版）
- 2024-2025学年清华大学版（2024）A版初中信息科技八年级下册（全册）知识点复习要点归纳
- 五年级下册数学期中必考易错题应用题六大类
- 密闭式静脉输血操作流程
- 审计案例第2章审计风险评估案例
- 2025年中国菠菜种植行业市场全景评估及发展战略规划报告
- 中国食物成分表标准版第6版
评论
0/150
提交评论