【备战蓝桥杯】----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 外设,有自…...

国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...