【动态规划/背包问题】背包问题第一阶段最终章:混合背包问题

简介: 【动态规划/背包问题】背包问题第一阶段最终章:混合背包问题

网络异常,图片无法展示
|


前言



今天是我们讲解 动态规划专题 中的「背包问题」的第十一篇。


今天将会学习「混合背包」问题,同时也是我们「背包问题」的第一阶段的最后一节。


今天首先会和大家回顾之前学过的三种背包问题。


然后通过一道「混合背包」问题,来将我们之前学的几种背包问题串联起来。


希望通过本篇内容,大家会对背包问题有更清晰的认识。


另外,我在文章结尾处列举了我所整理的关于背包问题的相关题目。


背包问题我会按照编排好的顺序进行讲解(每隔几天更新一篇,确保大家消化)。


你也先可以尝试做做,也欢迎你向我留言补充,你觉得与背包相关的 DP 类型题目 ~


回顾三种传统背包问题



前面我们已经学完了三种传统背包问题了。


这里再回顾一下三种传统背包:


  • 01 背包:强调每件物品**「只能选择一次」。对其进行「一维空间优化」并不能降低时间复杂度,进行「一维空间优化」时要求「容量维度“从大到小”进行遍历」**。
  • 完全背包:强调每件物品**「可以选择无限次」。对其进行「一维空间优化」具有数学意义,可以将时间复杂度从 降低到 ,进行「一维空间优化」时要求「容量维度“从小到大”进行遍历」**。
  • 多重背包:强调每件物品**「只能选择有限次」**。对其无论是进行「一维空间优化」还是「普通扁平化」都不能降低时间复杂度,要应用额外的优化手段:二进制优化单调队列优化


三种背包问题的**「难易程度」「递增」,但「重要程度」则是「递减」** 的。


虽然「多重背包」的 二进制优化单调队列优化 都比较 trick。


但其实「多重背包」并没有这么常见,以至于在 LeetCode 上我都没找到与「多重背包」相关的题目。


同时三种背包问题都有**「不超过」「恰好」**两种状态定义。


这两种状态定义只在「初始化」上有区别。


至于该如何初始化则要抓住 什么样的状态是合法的 :


  • 对于「不超过」的状态定义: 均为合法值 。
    代表不考虑任何物品,背包容量「不超过 」的所取得的最大价值为 。
  • 对于「恰好」的状态定义: 中只有 为合法值 ,其他值均为“无效值”。
    代表不考虑任何物品,只有背包容量「恰好为 」时所取得的最大价值为 ;其他容量「恰好为非 」是无法取得有效价值的(因为不考虑任何物品)。


总的来说,三种背包问题都很经典(本质上都是组合优化问题),以至于「背包问题」直接成为了一类的动态规划模型。


我的建议是三种背包都需要掌握。但如果实在要分侧重点的话,我更愿意你将大多数时间花在「01 背包」和「完全背包」上。


混合背包



给定物品数量 和背包容量 。第 件物品的体积是 ,价值是 ,可用数量为 :


  • 当 为 代表是该物品只能用一次
  • 当 为 代表该物品可以使用无限次
  • 当 为任意正整数则代表可用 次


求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。


基本分析



混合背包其实就是综合了「01 背包」、「完全背包」和「多重背包」三种传统背包问题。


我们知道在一维空间优化方式中「01 背包」将当前容量 按照“从大到小”进行遍历,而「完全背包」则是将当前容量 按照“从小到大”进行遍历。


同时「多重背包」可以通过「二进制优化」彻底转移成「01 背包」。


所以我们只需要根据第 个物品是「01 背包」物品还是「完全背包」物品,选择不同的遍历顺序即可。


代码:


class Solution {
    public int maxValue(int N, int C, int[] w, int[] v, int[] s) {
        // 构造出物品的「价值」和「体积」列表
        List<Integer> worth = new ArrayList<>();
        List<Integer> volume = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int type = s[i];
            // 多重背包:应用「二进制优化」转换为 0-1 背包问题
            if (type > 0) { 
                for (int k = 1; k <= type; k *= 2) {
                    type -= k;
                    worth.add(w[i] * k);
                    volume.add(v[i] * k);
                }
                if (type > 0) {
                    worth.add(w[i] * type);
                    volume.add(v[i] * type);
                }
            // 01 背包:直接添加
            } else if (type == -1) {
                worth.add(w[i]);
                volume.add(v[i]);
            // 完全背包:对 worth 做翻转进行标记
            } else {
                worth.add(-w[i]);
                volume.add(v[i]);
            }
        }
        // 使用「一维空间优化」方式求解三种背包问题
        int[] dp = new int[C + 1];
        for (int i = 0; i < worth.size(); i++) {
            int wor = worth.get(i);
            int vol = volume.get(i);
            // 完全背包:容量「从小到大」进行遍历
            if (wor < 0) { 
                for (int j = vol; j <= C; j++) {
                    // 同时记得将 worth 重新翻转为正整数
                    dp[j] = Math.max(dp[j], dp[j - vol] - wor); 
                }
            // 01 背包:包括「原本的 01 背包」和「经过二进制优化的完全背包」
            // 容量「从大到小」进行遍历
            } else { 
                for (int j = C; j >= vol; j--) {
                    dp[j] = Math.max(dp[j], dp[j - vol] + wor);
                }
            }
        }
        return dp[C];
    }
}
复制代码


就这样我们解决了这个混合背包问题。


先将一个「多重背包」问题通过「二进制优化」的思路,转化为「01 背包」问题。


然后根据物品是属于「01 背包」还是「完全背包」决定容量 是"从大到小"还是"从小到大"进行推算。


换句话说就是根据物品的类型不同,选择不同的转移方式。


总结



今天我们在学习「混合背包」之前先梳理了前面学的三种传统背包问题。


三种传统背包的主要区别在于「物品可被选择的次数」,其中「01 背包」的一维空间的优化方式是其余背包问题的基础。


对于「完全背包」和「多重背包」而言,一个可以选择「任意个数的物品」,另外一个则存在「选择物品的上界」。


这导致这两种背包问题在转移某个 时,其实本质是分别在求「整个前缀的最值」和「滑动窗口的最值」。


这就意味着「完全背包」可以直接通过一维空间优化降低时间复杂度;而「多重背包」则要通过「二进制优化」(减少总的物品数量)或者「单调队列优化」(实现直接求得滑动窗口最值)来降低时间复杂度。


最后



到这一节结束,我们就已经完成「背包问题」的第一阶段的学习了 🎉 🎉


接下来的「背包问题」更多的偏向于「多维」、「分组」、「有依赖」、「求方案数/具体方案」此类问题。


这类问题往往才是真正用来考察「背包思维」的题目,第一阶段的学习更多的是模板题,打基础用的。


继续加油吧 ~


另外,最近一段时间的公众号的更新频率确实下降了


不少同学通过各种渠道(LeetCode 评论区、知乎、公众号后台)催更 ...


但是我真的没有偷懒啦 🤣


这就来跟大家分享最近在忙些什么:


  1. 首先肯定是忙工作啦
  2. 然后是正在将内容整理成排版和顺序都比较合理的 pdf ,后面会公开出来给大家下载
  3. 最后一个则是彩蛋预告:最近在和 LeetCode 策划合作出两本 LeetBook  🎉 🎉 目前已经接近尾声,到时仍然会以「免费 & 非会员」的形式提供给大家 🤣 这样大家就能获得更好的学习体验啦 ~


敬请期待叭 ~


过了这一阵子后,公众号会恢复到「一周 3~4 篇」的更新频率滴 ~


背包问题(目录)



由于「背包问题」很多模板题在 LeetCode 上都没有模板题,同时公众号不能放外链,所以今晚建了一个背包仓库。


后面会给每篇文章配相应的原题地址,欢迎 mark ~


(持续更新)完整地址:github.com/SharingSour…


  1. 01背包 : 背包问题 第一讲
  2. 【练习】01背包 : 背包问题 第二讲
  3. 【学习&练习】01背包 : 背包问题 第三讲
  4. 完全背包 : 背包问题 第四讲
  5. 【练习】完全背包 : 背包问题 第五讲
  6. 【练习】完全背包 : 背包问题 第六讲
  7. 【练习】完全背包 : 背包问题 第七讲
  8. 多重背包 : 背包问题 第八讲
  9. 多重背包(优化篇)
  10. 【上】多重背包(优化篇): 背包问题 第九讲
  11. 【下】多重背包(优化篇): 背包问题 第十讲
  12. 混合背包 : 本篇
  13. 【练习】混合背包
  14. 分组背包
  15. 【练习】分组背包
  16. 多维背包
  17. 【练习】多维背包
  18. 树形背包
  19. 【练习篇】树形背包
  20. 背包求方案数
  21. 【练习】背包求方案数
  22. 背包求具体方案
  23. 【练习】背包求具体方案
  24. 泛化背包
  25. 【练习】泛化背包
  • [ ]
相关文章
|
SQL 安全 前端开发
maccms网站被挂马 根源问题在于SQL注入远程代码漏洞
目前苹果CMS官方在不断的升级补丁,官方最新的漏洞补丁对于目前爆发的新漏洞没有任何效果。更新补丁的用户网站还是会遭受到挂马的攻击,很多客户因此找到我们SINE安全寻求网站安全技术上的支持,针对该漏洞我们有着独特的安全解决方案以及防止挂马攻击的防护,包括一些未公开的maccms POC漏洞都有修复补丁
1038 0
maccms网站被挂马 根源问题在于SQL注入远程代码漏洞
|
Java 关系型数据库 中间件
分库分表(3)——ShardingJDBC实践
分库分表(3)——ShardingJDBC实践
938 0
分库分表(3)——ShardingJDBC实践
|
移动开发 监控 小程序
钉钉工作台开放能力建设阶段性总结
工作台的平台化开放能力建设已经走了近3年的时间,包括定制工作台的开放、工作台模板的开放、工作台组件的开放等等。本文主要是对过程中一些关键能力的总结和思考,欢迎交流。工作台的类型工作台作为企业业务数字化的统一门户,是组织用于提升管理效率、实现业务在线的平台。工作台的组织就是钉钉上的组织,针对不同的组织规模,提供了多种类型工作台:角色工作台、行业工作台和自定义工作台。角色工作台是对不同的角色,例如财务
1312 0
钉钉工作台开放能力建设阶段性总结
|
12月前
|
Cloud Native 持续交付 云计算
云计算的未来:探索云原生技术的崛起与影响
【10月更文挑战第9天】 在当今数字化转型的浪潮中,云计算已成为推动企业创新和效率提升的关键力量。随着技术的进步和市场需求的演变,一种新兴的技术趋势——云原生,正逐渐崭露头角,引领着云计算进入一个全新的发展阶段。本文将深入探讨云原生的概念、核心原则、关键技术以及它如何改变企业的运营模式和业务策略。通过分析云原生技术的优势、挑战和未来趋势,我们将揭示这一技术变革背后的深层含义,以及它如何塑造未来的数字生态系统。
|
12月前
|
机器学习/深度学习 移动开发 自然语言处理
基于人工智能技术的智能导诊系统源码,SpringBoot作为后端服务的框架,提供快速开发,自动配置和生产级特性
当身体不适却不知该挂哪个科室时,智能导诊系统应运而生。患者只需选择不适部位和症状,系统即可迅速推荐正确科室,避免排错队浪费时间。该系统基于SpringBoot、Redis、MyBatis Plus等技术架构,支持多渠道接入,具备自然语言理解和多输入方式,确保高效精准的导诊体验。无论是线上医疗平台还是大型医院,智能导诊系统均能有效优化就诊流程。
367 0
|
网络协议 物联网 网络性能优化
物联网江湖风云变幻!MQTT CoAP RESTful/HTTP XMPP四大门派谁主沉浮?
【9月更文挑战第3天】物联网(IoT)的兴起催生了多种通信协议,如MQTT、CoAP、RESTful/HTTP和XMPP,各自适用于不同场景。本文将对比这些协议的特点、优缺点,并提供示例代码。MQTT轻量级且支持QoS,适合大规模部署;CoAP基于UDP,适用于低功耗网络;RESTful/HTTP易于集成但不适合资源受限设备;XMPP支持双向通信,适合复杂交互应用。通过本文,开发者可更好地选择合适的物联网通信协议。
246 2
|
12月前
|
存储 安全 Windows
电脑桌面文件不见了怎么恢复?8个方法帮你解决问题
电脑桌面文件突然不见了凭空消失了怎么恢复?电脑桌面文件日常使用电脑时,很多用户喜欢将重要文件、快捷方式存放在桌面上,以方便快速访问。然而,有时我们会突然发现桌面上的文件不见了。桌面文件消失可能有多种原因,例如误删除、系统更新、设置变更等。今天给大家介绍一些桌面文件丢失的常见的原因以及如何找回丢失的文件。
|
机器学习/深度学习
西瓜书机器学习AUC与ℓ-rank(loss)的联系理解以及证明(通俗易懂)
西瓜书机器学习AUC与ℓ-rank(loss)的联系理解以及证明(通俗易懂)
553 0
|
存储 网络协议 安全
计网: 一条QQ信息在发送中会经历了什么
计网: 一条QQ信息在发送中会经历了什么
281 0
|
机器学习/深度学习 人工智能 文字识别
漫画党的福利——将图片转换成漫画风格 API,附超多免费可用API 推荐(四)
漫画党的福利——将图片转换成漫画风格 API,附超多免费可用API 推荐
508 0
漫画党的福利——将图片转换成漫画风格 API,附超多免费可用API 推荐(四)