【备战蓝桥杯】----01背包问题(动态规划)
🌹作者:云小逸
📝个人主页:云小逸的主页
📝Github:云小逸的Github
🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前,其次就是现在!学会自己和解,与过去和解,努力爱自己。==希望春天来之前,我们一起面朝大海,春暖花开!==🤟
👏专栏:C++👏 👏专栏:Java语言👏👏专栏:Linux学习👏
👏专栏:C语言初阶👏👏专栏:数据结构👏👏专栏:备战蓝桥杯👏
文章目录
- 前言
- 0-1背包问题
- 二维解法
- 状态定义
- 状态转移方程
- 详细讲解:
- f数组:
- f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
- 代码实现
- 一维解法
- 状态定义
- 状态转移方程
- 详细解释:
- int j = m; j >= v[i]; j--
- f[j] = max(f[j], f[j - v[i]] + w[i]);
- 代码实现
- 总结
- 二维解法和一维解法都是经典的背包问题解法,二者的时间复杂度都是 O(nm)O(nm)O(nm),但是一维解法的空间复杂度为 O(m)O(m)O(m),比二维解法的 O(nm)O(nm)O(nm) 更优秀。因此,在实际应用中,一维解法更为常用
- 最后
-
-
前言
今天我们来学习一下一个经典Dp问题----背包问题,这里将详细介绍背包问题的二维解法和一维解法。码字不易,请多多支持。
——————————————————————————————
0-1背包问题
背包问题是一个经典的动态规划问题,其基本形式是:有一个容量为 VVV 的背包和 nnn 个物品,每个物品有一个体积 viv_ivi 和一个价值 wiw_iwi。要求选择若干物品装入背包,使得装入背包中物品的总价值最大。其中每个物品只能选择装入一次。
二维解法
状态定义
设 f(i,j)f(i,j)f(i,j) 表示前 iii 个物品,体积不超过 jjj 的情况下可以获得的最大价值。
状态转移方程
对于第 iii 个物品,有两种选择:
- 不放入背包,此时背包的最大价值为 f(i−1,j)f(i-1,j)f(i−1,j);
- 放入背包,此时背包的最大价值为 f(i−1,j−vi)+wif(i-1,j-v_i)+w_if(i−1,j−vi)+wi。
因此,状态转移方程为:
f(i,j)=max{f(i−1,j),f(i−1,j−vi)+wi}f(i,j)=\max\{f(i-1,j),f(i-1,j-v_i)+w_i\}f(i,j)=max{f(i−1,j),f(i−1,j−vi)+wi}
详细讲解:
f数组:
在背包问题中,f数组一般表示状态转移方程中的“状态”,即f(i,j)f(i,j)f(i,j)表示在前iii个物品中,背包容量为jjj时的最大价值。也就是说,f(i,j)f(i,j)f(i,j)表示在当前背包容量为jjj的情况下,前iii个物品能够获得的最大价值。在动态规划中,我们需要通过状态转移方程来不断更新f(i,j)f(i,j)f(i,j)的值,最终得到背包问题的最优解。
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
这条语句是背包问题中的状态转移方程,表示在背包容量为 j 时,前 i 个物品能够获得的最大价值。
具体来说,f[i][j] 表示前 i 个物品,在背包容量为 j 时能够获得的最大价值。而根据背包问题的定义,第 i 个物品有两种选择,要么不装入背包,此时最大价值为 f[i-1][j];要么装入背包,此时最大价值为 f[i-1][j-v[i]] + w[i],其中 f[i-1][j-v[i]] 表示背包容量为 j-v[i] 时前 i-1 个物品的最大价值,w[i] 表示第 i 个物品的价值。因此,f[i][j] 就是这两种选择中的最大值。
代码实现
#include<bits/stdc++.h>using namespace std;const int MAXN = 1005;
int v[MAXN]; // 存储物品体积
int w[MAXN]; // 存储物品价值
int f[MAXN][MAXN]; // f[i][j]表示在背包容量为j的情况下,前i个物品的最大价值int main()
{int n, m; cin >> n >> m; // 输入物品数量和背包容量// 输入每个物品的体积和价值for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];// 动态规划求解for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){// 当前背包容量装不下第i个物品,则最大价值为前i-1个物品的最大价值f[i][j] = f[i - 1][j];// 当前背包容量能够装下第i个物品,需要对是否选择第i个物品进行决策if(j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);} cout << f[n][m] << endl; // 输出最大价值return 0;
}
一维解法
状态定义
设 f(j)f(j)f(j) 表示体积不超过 jjj 的情况下可以获得的最大价值。
状态转移方程
对于第 iii 个物品,有两种选择:
- 不放入背包,此时背包的最大价值为 f(j)f(j)f(j);
- 放入背包,此时背包的最大价值为 f(j−vi)+wif(j-v_i)+w_if(j−vi)+wi。
因此,状态转移方程为:
f(j)=max{f(j),f(j−vi)+wi}f(j)=\max\{f(j),f(j-v_i)+w_i\}f(j)=max{f(j),f(j−vi)+wi}
详细解释:
int j = m; j >= v[i]; j–
这里的意思是从大到小枚举体积,因为在计算当前物品的最大价值时,需要用到之前物品的最大价值,而之前物品的最大价值可能已经被更新过,所以需要从大到小枚举体积,保证当前物品的体积不会影响之前物品的最大价值。同时,体积从大到小枚举也可以保证每个物品只被考虑一次,避免重复计算。
f[j] = max(f[j], f[j - v[i]] + w[i]);
在背包问题中,f[j]表示体积不超过j的情况下可以获得的最大价值。而f[j]的计算需要考虑两种情况:
- 不选第i个物品,此时f[j]的价值为f[j],即前i-1个物品的最大价值。
- 选第i个物品,此时f[j]的价值为f[j - v[i]] + w[i],即前i-1个物品在剩余容量为j - v[i]的情况下的最大价值加上第i个物品的价值w[i]。
因此,f[j]的值应该为这两种情况的最大值,即f[j] = max(f[j], f[j - v[i]] + w[i])。
代码实现
#include<bits/stdc++.h>using namespace std;const int MAXN = 1005;
int v[MAXN]; // 物品体积
int w[MAXN]; // 物品价值
int f[MAXN]; // f[j]表示体积不超过j的情况下可以获得的最大价值int main()
{int n, m; cin >> n >> m; // n表示物品个数,m表示背包容量// 输入每个物品的体积和价值for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];// 01背包一维解法for(int i = 1; i <= n; i++) for(int j = m; j >= v[i]; j--)f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl; // 输出最大价值return 0;
}
总结
二维解法和一维解法都是经典的背包问题解法,二者的时间复杂度都是 O(nm)O(nm)O(nm),但是一维解法的空间复杂度为 O(m)O(m)O(m),比二维解法的 O(nm)O(nm)O(nm) 更优秀。因此,在实际应用中,一维解法更为常用
最后
十分感谢你可以耐着性子把它读完和我可以坚持写到这里,送几句话,对你,也对我:
1. 短期拼智力、中期拼毅力、长期拼体力。不要觉得自己落后了,用马拉松的心态,过自己的一生,你慢了一时一分,别焦虑。要看你我是否七八十岁,还有扛着锄头上山种橙子的那种勇气。
2.人间的美好,是3月的风,6月的雨,9月的云和12月的雪。
3.痛苦是对的。 痛苦源于对现状的不满,只有不满足于现状的人才会痛苦,痛苦才会深刻。痛苦的人,才有欲望去改造这一切。焦虑也是对的。焦虑是因为你想做得更好,说明你追求高,说明你眼界高,说明你知识多。痛苦和焦虑的人才是最真实的你我。
4.人生没有办法做到始终一帆风顺,也没有办法万事如意。但凡是你渴望的,都是你拿不到的;但凡是你乞求的,都是你实现不了的。 年轻人才会悔恨过去,能够坦然接受这一切的都是智者。
5.人生有一段路,一定要自己去走。 黎明前那一段天是最黑的, 但是只要再熬那么一会儿,天就亮了。 耐心就是智慧。 就连太阳光到达地球需要八分钟,你急什么呢? 那可是宇宙第一速度 。
最后如果觉得我写的还不错,请不要忘记点赞✌,收藏✌,加关注✌哦(。・ω・。)
愿我们一起加油,奔向更美好的未来,愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油,为自己点赞!
相关文章:

【备战蓝桥杯】----01背包问题(动态规划)
🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前…...
Golang1.18新特性介绍——泛型
社区长期高呼的泛型特性在Golang 1.18中终于正式发布,Go泛型实现与传统的C有较大差异,更像Rust的泛型实现。本文详细介绍Golang泛型及其特性,包括泛型语法、类型参数、类型约束、类型近似以及constraints包提供内置类型等。 最近写Dao代码&am…...

【SpringBoot17】SpringBoot中使用Quartz管理定时任务
定时任务在系统中用到的地方很多,例如每晚凌晨的数据备份,每小时获取第三方平台的 Token 信息等等,之前我们都是在项目中规定这个定时任务什么时候启动,到时间了便会自己启动,那么我们想要停止这个定时任务的时候&…...

杨辉三角形 (蓝桥杯) JAVA
目录题目描述:暴力破解(四成):二分法破解(满分):题目描述: 下面的图形是著名的杨辉三角形: 如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如…...

AI制药 - AlphaFold Multimer 的 MSA Pairing 源码
目前最新版本是v2.3.1,2023.1.12 AlphaFold multimer v1 于 2021 年 7 月发布,同时发表了一篇描述其方法和结果的论文。AlphaFold multimer v1 使用了与 AlphaFold 单体相同的模型结构和训练方法,但增加了一些特征和损失函数来处理多条链。Al…...

TitanIDE:云原生开发到底强在哪里?
原文作者:行云创新技术总监 邓冰寒 引言 是一种新的软件开发方法,旨在构建更可靠、高效、弹性、安全和可扩展的应用程序。与传统的应用程序开发方式不同,云原生是将开发环境完全搬到云端,构建一站式的云原生开发环境。云原生的开…...
单片机常用完整性校验算法
一、前言 单片机在开发过程中经常会遇到大文件传输,或者大量数据传输,在一些工业环境下,数据传输并不是很稳定,如何检验数据的完整性就是个问题,这里简单介绍一下单片机常用的几种数据完整性校验方法。 二、CheckSum校…...

Anaconda 的安装配置及依赖项的内外网配置
在分享anaconda 的安装配置及使用前,我们必须先明白anaconda是什么;Anaconda是一个开源的Python发行版本。两者区别在于前者是一门编程语言,后者相当于编程语言中的工具包。 由于python自身缺少numpy、matplotlib、scipy、scikit-learn等一系…...

p84 CTF夺旗-PHP弱类型异或取反序列化RCE
数据来源 文章参考 本课重点: 案例1:PHP-相关总结知识点-后期复现案例2:PHP-弱类型对比绕过测试-常考点案例3:PHP-正则preg_match绕过-常考点案例4:PHP-命令执行RCE变异绕过-常考点案例5:PHP-反序列化考题…...

2022财报逆转,有赞穿透迷雾实现突破
2022年,商家经营面临困难。但在一些第三方服务商的帮助下,也有商家取得了逆势增长。 2023年3月23日,有赞发布2022年业绩报告,它帮助许多商家稳住了一整年的经营。2022年,有赞门店SaaS业务的GMV达到425亿元,…...

蓝桥杯 - 求组合数【C(a,b)】+ 卡特兰数
文章目录💬前言885. 求组合数 I C(m,n) 【dp】886 求组合数 II 【数据大小10万级别】 【费马小定理快速幂逆元】887. 求组合数 III 【le18级别】 【卢卡斯定理 逆元 快速幂 】888.求组合数 IV 【没有%p -- 高精度算出准确结果】 【分解质因数 高精度乘法 --只用一…...

膳食真菌在癌症免疫治疗中的作用: 从肠道微生物群的角度
谷禾健康 癌症是一种恶性肿瘤,它可以发生在人体的任何部位,包括肺、乳房、结肠、胃、肝、宫颈等。根据世界卫生组织的数据,全球每年有超过1800万人被诊断出患有癌症,其中约有1000万人死于癌症。癌症已成为全球范围内的主要健康问题…...
怎么将模糊的照片变清晰
怎么将模糊的照片变清晰?珍贵的照片每个人都会有,而遇到珍贵的照片变模糊了,相信会让人很苦恼的。那么有没有办法可以解决呢?答案是有的,我们可以用工具让模糊的照片变得清晰。下面就来分享一些让模糊的照片变清晰的方法,有兴趣…...

【软件测试】基础知识第一篇
文章目录一. 什么是软件测试二. 测试和调试的区别三. 什么是测试用例四. 软件的生命周期五. 软件测试的生命周期一. 什么是软件测试 软件测试就是验证软件产品特性是否满足用户的需求。 那需求又是什么呢?在多数软件公司,会有两种需求,一种…...

【百面成神】java web基础7问,你能坚持到第几问
前 言 🍉 作者简介:半旧518,长跑型选手,立志坚持写10年博客,专注于java后端 ☕专栏简介:纯手打总结面试题,自用备用 🌰 文章简介:java web最基础、重要的8道面试题 文章目…...

Centos7安装、各种环境配置和常见bug解决方案,保姆级教程(更新中)
文章目录前言一、Centos7安装二、各种环境配置与安装2.1 安装net-tools(建议)2.2 配置静态网络(建议)2.1 修改Centos7的时间(建议)2.2 Centos7系统编码问题2.3 vim安装(建议)2.4 解决…...

【C++进阶】智能指针
文章目录为什么需要智能指针?内存泄漏什么是内存泄漏,内存泄漏的危害内存泄漏分类(了解)如何避免内存泄漏智能指针的使用及原理smart_ptrauto_ptrunique_ptrshared_ptr线程安全的解决循环引用weak_ptr删除器为什么需要智能指针&am…...

软件测试面试题 —— 整理与解析(3)
😏作者简介:博主是一位测试管理者,同时也是一名对外企业兼职讲师。 📡主页地址:🌎【Austin_zhai】🌏 🙆目的与景愿:旨在于能帮助更多的测试行业人员提升软硬技能…...
springboot常用的20个注解
Spring Boot方式的项目开发已经逐步成为Java应用开发领域的主流框架,它不仅可以方便地创建生产级的Spring应用程序,还能轻松地通过一些注解配置与目前比较火热的微服务框架SpringCloud集成, 而Spring Boot 之所以能够轻松地实现应的创建及与…...
USB组合设备——带鼠标功能的键盘
文章目录带鼠标功能的键盘一个接口实现报告描述符示例多个接口实现复合设备和组合设备配置描述符集合的实现报告的返回附 STM32 枚举日志复合设备:Compound Device 内嵌 Hub 和多个 Function,每个 Function 都相当于一个独立的 USB 外设,有自…...

VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...

微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...