代码随想录算法训练营第四十四天 | 01背包问题 二维、 01背包问题 一维、416. 分割等和子集

01背包问题 二维

代码随想录

视频讲解:带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

 1.dp数组定义

dp[i][j]  下标为[0,i]之间的物品,任取放容量为j的背包的最大价值

2.递推公式

不放物品i: dp[i-1][j]  去看是否放i-1,还是有j的容量给i-1去放

放物品i : dp[i-1][j-weight[i]] + value[i],放了物品i,那么就只有j-weight[i]的容量给i-1个物品去放了,同时要加上我这个物体的价值

 dp[i][j] = max(上面两个),取最大价值

3.数组初始化

首先看,i是由i-1推出来的,j是否左上的某一个格子或者正上推出来的(背包剩余容量)

dp[i][0] = 0,背包的容量为0,不管放哪个,价值都为0

dp[0][j] , 当背包可以装下这个物品开始,dp[0][j]就等于这个物品的价值,装不下就为0

4.遍历顺序

for(i<weight.size() )   物品

  for(j<=bagweight )    背包

对于二维数组实现的01背包,物品和背包的遍历顺序是可以颠倒的,因为左上方和上方是有值的

循环体内是正序还是倒序都是可以的,因为都是根据上一行的数据来进行推导的

01背包问题 一维

代码随想录

视频讲解:带你学透01背包问题(滚动数组篇) | 从此对背包问题不再迷茫!_哔哩哔哩_bilibili

因为这里的i层都是由i-1层推到出来的,因此只需要一个一行的一维滚动数组来维护就可以了,不需要整个二维数组

1. dp[j] 容量为j的背包的最大价值为dp[j]

2.递推公式

不放物品i,就是自己dp[j],也就是把上一层数据拷贝下来

放物品i , dp[j-weight[i]] + value[i]

dp[j] = max(上面两个)

3.初始化

dp[0]=0 , 背包容量为0的时候,最大价值为0

非零下标都是初始化为0,因为为其他的话,会覆盖掉递推公式中算出来的值

4.遍历顺序

for(i<weight.size())  物品

  for(j=bagweight,j>=weight[0] )  背包

采用倒序,是为了防止物品重复选取,比较的数据来自上一轮

正序遍历就是用同一个物品塞满背包,每次覆盖的数据都是同一个物品塞满的情况

dp【i】【j】的更新只与dp【i-1】【j】和dp【i-1】【j-weight_i】左上角这两个数据有关,而与右边的数据无关,那么从右向左遍历,遍历时左边的数据还是上一行的数据没有更新, 这样子用一行数组很好的实现了我们的最终目的

在一维中,只能先遍历物品,再遍历背包

如果先遍历背包,再遍历物品,那记录的就是只有一个物品

 

416. 分割等和子集

代码随想录

视频讲解:动态规划之背包问题,这个包能装满吗?| LeetCode:416.分割等和子集_哔哩哔哩_bilibili

解题思路

本题元素只能使用1次,并且看能不能装满11这个背包

1.dp[j] 容量为j的背包的最大价值,本题最大价值和重量,都是数字本身

2. dp[j] = max(dp[j], dp[j-nums[i] + nums[i]])

3.dp[0] = 0;非零下标,初始为非负整数的最小值,也就是0,因为是由max得来的

4.遍历顺序,先遍历物品,再遍历背包,背包是倒序,j要大于等于nums[i],且每个物品只能使用一次

最后去判断背包是否装满了 dp[target] == target

class Solution {
public:bool canPartition(vector<int>& nums) {int sum =0;for(int i: nums)sum+=i;if(sum%2!=0) return false;int  target = sum/2;vector<int> dp(target+1,0);for(int i=0 ; i< nums.size(); i++)   //物品{for(int j = target; j>=nums[i] ; j--)    //背包{dp[j] = max(dp[j], dp[j- nums[i] ] + nums[i] );   //这题物品和价值是一样的}}if(dp[target]==target) return true;else return false;}
};

收获

今天掌握了01背包的理论基础,本尝试应用

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/336812.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C# try catch异常捕获

异常捕获 执行过程&#xff1a;try中的代码没有出现异常&#xff0c;则catch里面不会自行&#xff0c;如果try中代码出现异常&#xff0c;则后面的代码都不执行&#xff0c;直接跳到catch中的代码执行。 // try catch 可以捕获多个错误&#xff0c; try...catch...catch.... …

01 - Maven入门安装

目录 1、软件下载地址 2、安装的版本 3、安装的条件 4、软件的结构 5、Maven环境配置 5.1、配置MAVEN_HOME 5.2、配置Path 5.3、命令测试&#xff08;cmd窗口&#xff09; 6、Maven的功能配置 6.1、配置本地仓库地址 6.2、配置国内阿里镜像 6.3、配置jdk8版本项目构…

ChaosBlade混沌测试实践

ChaosBlade: 一个简单易用且功能强大的混沌实验实施工具 官方仓库&#xff1a;https://github.com/chaosblade-io/chaosblade 1. 项目介绍 ChaosBlade 是阿里巴巴开源的一款遵循混沌工程原理和混沌实验模型的实验注入工具&#xff0c;帮助企业提升分布式系统的容错能力&…

【HTML】通过焦点,获取部分上下文内容

【HTML】通过焦点&#xff0c;获取部分上下文内容 需求 用户从页面中选择部分文字描述&#xff0c;获取这段选中文字&#xff0c;并获取该文字、上两段、下两段内容&#xff0c;作为上下文输入 效果说明 选中绿色框内文字&#xff0c;将黄色框内文字作为上下文传递 代码实…

网络安全岗秋招面试题及面试经验分享

Hello&#xff0c;各位小伙伴&#xff0c;我作为一名网络安全工程师曾经在秋招中斩获&#x1f51f;个offer&#x1f33c;&#xff0c;并在国内知名互联网公司任职过的职场老油条&#xff0c;希望可以将我的面试的网络安全大厂面试题和好运分享给大家~ 转眼2024年秋招又快到了金…

【传知代码】MonoCon解读与复现(论文复现)

前言&#xff1a;在快速发展的计算机视觉领域&#xff0c;单目视觉&#xff08;Monocular Vision&#xff09;技术凭借其独特的优势和广泛的应用前景&#xff0c;逐渐成为了研究的热点。MonoCon作为单目视觉领域的一项重要技术&#xff0c;其独特的算法设计和高效的性能表现&am…

《Kubernetes部署篇:基于麒麟V10+ARM64架构部署harbor v2.4.0镜像仓库》

总结&#xff1a;整理不易&#xff0c;如果对你有帮助&#xff0c;可否点赞关注一下&#xff1f; 更多详细内容请参考&#xff1a;企业级K8s集群运维实战 一、环境信息 K8S版本 操作系统 CPU架构 服务版本 1.26.15 Kylin Linux Advanced Server V10 ARM64 harbor v2.4.0 二、部…

Python爬虫实战(实战篇)—16获取【百度热搜】数据—写入Ecel(附完整代码)

文章目录 专栏导读背景结果预览1、爬取页面分析2、通过返回数据发现适合利用lxmlxpath3、继续分析【小说榜、电影榜、电视剧榜、汽车榜、游戏榜】4、完整代码总结 专栏导读 &#x1f525;&#x1f525;本文已收录于《Python基础篇爬虫》 &#x1f251;&#x1f251;本专栏专门…

windows 执行node报错 800A1391

在项目下执行node -v的时候&#xff0c;抛了这个错误&#xff0c;一开始没发现有啥问题 现在一看&#xff0c;这个报错里的node怎么是个文件... 出现这个问题&#xff0c;是因为项目下&#xff0c;有个同名的文件叫node.js&#xff0c;搞得windows一时不知道是想打开node.js文…

基于 React + Nest 全栈开发的后台系统

Xmw Admin 基于 React Nest 全栈开发的后台系统 &#x1fab4; 项目简介 &#x1f3af; 前端技术栈&#xff1a; React、Ant Design、Umi、TypeScript&#x1f3af; 后端技术栈&#xff1a; Nest.js、Sequelize、Redis、Mysql&#x1f61d; 线上预览&#xff1a; https://r…

爱堡集团数智掘金—共绘上市蓝图

&#xff08;本台记者报&#xff09;2024年5月26日爱堡集团在浙江省杭州市上城区瑞莱克斯大酒店隆重召开规模达500人的盛会。这场聚焦智慧与创新的会议&#xff0c;旨在加速爱堡集团的数智化转型进程&#xff0c;并为其上市之路绘制蓝图&#xff0c;吸引了众多行业领袖和媒体的…

Claude 3可使用第三方API,实现业务流程自动化

5月31日&#xff0c;著名大模型平台Anthropic宣布&#xff0c;Claude3模型可以使用第三方API和工具。 这也就是说&#xff0c;用户通过文本提问的方式就能让Claude自动执行多种任务&#xff0c;例如&#xff0c;从发票中自动提取姓名、日期、金额等&#xff0c;该功能对于开发…

做外贸,怎么选国外服务器?

不管是新手还是外贸老司机&#xff0c;大家都知道要用海外服务器来做外贸网站&#xff0c;无论外贸独立站的客户是欧美、东南亚、还是非洲&#xff0c;都不能选择国内机房的服务器&#xff0c;必须选择海外服务器&#xff0c;这是共识。 但是今天&#xff0c;我要告诉大家一个…

过敏者的福音:猫毛克星大揭秘!使用宠物空气净化器效果如何?

对于猫毛过敏者来说&#xff0c;家中爱宠的陪伴与过敏的困扰并存&#xff0c;给他们的日常生活带来了极大的不便。猫毛过敏者常常因为与猫咪接触后出现打喷嚏、鼻塞、眼睛发痒等症状而苦恼&#xff0c;严重时甚至可能影响到他们的呼吸健康。 然而&#xff0c;这并不意味着猫毛…

Windows系统安装openvino(2024.1.0)

一、openvino下载&#xff1a; 下载地址&#xff1a;下载英特尔发行版 OpenVINO 工具套件 (intel.cn) 下载完之后将压缩包解压&#xff0c;然后重命名文件夹为openvino_2024.1.0。 二、环境配置 以python环境为例&#xff1a;&#xff08;建议使用moniconda虚拟环境来安装&am…

【python】OpenCV—Color Detection

学习来自 如何使用 OpenCV Python 检测颜色 import cv2 import numpy as npdef red_hsv(img, saveFalse):lower_hsv1 np.array([0, 175, 20])higher_hsv1 np.array([10, 255, 255])lower_hsv2 np.array([170, 175, 20])higer_hsv2 np.array([10, 255, 255])mask1 cv2.inR…

STM32--ADC

一、简介 *ADC&#xff08;Analog-Digital Converter&#xff09;模拟-数字转换器 *ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量&#xff0c;建立模拟电路到数字电路的桥梁 *12位逐次逼近型ADC&#xff0c;1us转换时间 *输入电压范围&#xff1a;0~3.3V&…

鸿蒙ArkTS声明式开发:跨平台支持列表【背景设置】 通用属性

背景设置 设置组件的背景样式。 说明&#xff1a; 开发前请熟悉鸿蒙开发指导文档&#xff1a; gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md点击或者复制转到。 从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版…

备份数据怎么恢复?从入门到精通,2个技巧读懂!

在数字时代&#xff0c;数据的重要性不言而喻。无论是个人还是企业&#xff0c;数据都是我们生活和工作的核心&#xff0c;但由于各种原因&#xff0c;数据丢失的情况时有发生。为了应对这种情况&#xff0c;备份数据成为了一个必要的措施。可当数据真的丢失时&#xff0c;备份…

3D工业视觉

前言 本文主要介绍3D视觉技术、工业领域的应用、市场格局等&#xff0c;主要技术包括激光三角测量、结构光、ToF、立体视觉。 一、核心内容 3D视觉技术满足工业领域更高精度、更高速度、更柔性化的需求&#xff0c;扩大工业自动化的场景。 2D视觉技术基于物体平面轮廓&#…