代码随想录算法训练营第四十四天 | 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背包的理论基础,本尝试应用
相关文章:
代码随想录算法训练营第四十四天 | 01背包问题 二维、 01背包问题 一维、416. 分割等和子集
01背包问题 二维 代码随想录 视频讲解:带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili 1.dp数组定义 dp[i][j] 下标为[0,i]之间的物品&…...
redis常见使用场景
文章目录 redis常见使用场景全局ID位统计购物车用户消息时间线timeline抽奖商品筛选分布式锁限流redis实现计数器排行榜消息队列redis 如何实现延时队列 redis生产常用的场景 redis常见使用场景 Redis 是一种高性能的内存数据库,广泛应用于各种场景中。以下是 Redi…...
模糊C均值(FCM)算法更新公式推导
模糊C均值(FCM)算法更新公式推导 目标函数 FCM的目标函数为: J m ∑ i 1 n ∑ j 1 k u i j m ∥ x i − c j ∥ 2 J_m \sum_{i1}^n \sum_{j1}^k u_{ij}^m \|x_i - c_j\|^2 Jmi1∑nj1∑kuijm∥xi−cj∥2 其中: …...
金融创新浪潮下的拆分盘投资探索
随着数字化时代的步伐加速,金融领域正经历着前所未有的变革。在众多金融创新中,拆分盘作为一种新兴的投资模式,以其独特的增长机制,吸引了投资者的广泛关注。本文将对拆分盘的投资逻辑进行深入剖析,并结合具体案例&…...
一份不知道哪里来的第十五届国赛模拟题
这是一个不知道来源的模拟题目,没有完全完成,只作代码记录,不作分析和展示,极其冗长,但里面有长按短按双击的复合,可以看看。 目录 题目代码底层驱动主程序核心代码关键:双击单击长按复合代码 …...
机器人动力学模型与MATLAB仿真
机器人刚体动力学由以下方程控制!!! startup_rvc mdl_puma560 p560.dyn 提前计算出来这些“disturbance”,然后在控制环路中将它“抵消”(有时候也叫前馈控制) 求出所需要的力矩,其中M项代表克服…...
SAPUI5基础知识3 - 引导过程(Bootstrap)
1. 背景 在上一篇博客中,我们已经建立出了第一个SAPUI5项目,接下来,我们将为这个项目添加引导过程。 在动手练习之前,让我们先解释一下什么引导过程。 1.1 什么是引导过程? 在计算机科学中,引导过程也称…...
ABAP 借助公司封装的钉钉URL,封装的RFC给钉钉发送消息
FUNCTION ZRFC_BC_SMSSEND_DINGTALK. *"---------------------------------------------------------------------- *"*"本地接口: *" IMPORTING *" VALUE(DESTUSRID) TYPE CHAR255 *" VALUE(CONTENT) TYPE CHAR255 *&quo…...
登录校验及全局异常处理器
登录校验 会话技术 会话:用户打开浏览器,访问web服务器的资源,会话建立,直到有一方断开连接,会话结束.在一次会话中可以包含多次请求和响应会话跟踪:一种维护浏览器状态的方法,服务器需要识别多次请求是否来自于同一浏览器,以便在同一次会话请求间共享数据会话跟踪方案 客户端…...
计算机视觉与模式识别实验1-2 图像的形态学操作
文章目录 🧡🧡实验流程🧡🧡1.图像膨胀2.图像腐蚀3.膨胀与腐蚀的综合使用4.对下面二值图像的目标提取骨架,并分析骨架结构。 🧡🧡全部代码🧡🧡 🧡🧡…...
【前端每日基础】day31——uni-app
uni-app 开发详细介绍 基本概念 uni-app:uni-app 是一个使用 Vue.js 开发多端应用的框架,可以编译到微信小程序、支付宝小程序、百度小程序、字节跳动小程序、H5、App等多个平台。 跨平台:一次开发,多端部署。通过条件编译实现多…...
云动态摘要 2024-05-31
给您带来云厂商的最新动态,最新产品资讯和最新优惠更新。 最新优惠与活动 [1.5折起]年中盛惠--AI分会场 腾讯云 2024-05-30 人脸核身、语音识别、文字识别、数智人、腾讯混元等热门AI产品特惠,1.5折起 云服务器ECS试用产品续用 阿里云 2024-04-14 云…...
Oracle数据块如何存储真实数据
上周休假了几天,颓废了,没有输出。今天写一点内容。 先抛出一个问题。表中的数据在Oracle数据块中是如何存储的呢?今天简单说一下这个问题。通常数据库中的表会存储字符,数字,日期 这3种常见的数据类型。下面的例子就用这3种数据类型作说明 首先,Oracle数据块底层存储这…...
【WEB前端2024】开源智体世界:乔布斯3D纪念馆-第30课-门的移动动画
【WEB前端2024】开源智体世界:乔布斯3D纪念馆-第30课-门的移动动画 使用dtns.network德塔世界(开源的智体世界引擎),策划和设计《乔布斯超大型的开源3D纪念馆》的系列教程。dtns.network是一款主要由JavaScript编写的智体世界引擎…...
智能化改造给企业带来的实际效果
1. 提高生产效率:通过自动化和智能化的生产线,减少人工操作,显著提升单位时间内的生产量。 2. 提升产品质量:智能化改造通过精确控制生产过程,减少人为错误,提高产品的一致性和可靠性。 3. 降低生产成本&am…...
深度学习-语言模型
深度学习-语言模型 统计语言模型神经网络语言模型语言模型的应用序列模型(Sequence Model)语言模型(Language Model)序列模型和语言模型的区别 语言模型(Language Model)是自然语言处理(NLP&…...
微型导轨在自动化制造中有哪些优势?
微型导轨在自动化制造中发挥重要作用,能够满足自动化设备制造中对精度要求较高的工艺环节。适用于自动装配线、自动检测设备和机器人操作等环节,推动了行业的进步与发展。那么,微型导轨在使用中有哪些优势呢? 1、精度高和稳定性强…...
探索气象数据的多维度三维可视化:PM2.5、风速与高度分析
探索气象数据的多维度可视化:PM2.5、风速与高度分析 摘要 在现代气象学中,数据可视化是理解复杂气象模式和趋势的关键工具。本文将介绍一种先进的数据可视化技术,它能够将PM2.5浓度、风速和高度等多维度数据以直观和动态的方式展现出来。 …...
【传知代码】双深度学习模型实现结直肠癌检测(论文复现)
前言:在医学领域,科技的进步一直是改变人类生活的关键驱动力之一。随着深度学习技术的不断发展,其在医学影像诊断领域的应用正日益受到关注。结直肠癌是一种常见但危害极大的恶性肿瘤,在早期发现和及时治疗方面具有重要意义。然而…...
平衡二叉树的应用举例
AVL 是一种自平衡二叉搜索树,其中任何节点的左右子树的高度之差不能超过 1。 AVL树的特点: 1、它遵循二叉搜索树的一般属性。 2、树的每个子树都是平衡的,即左右子树的高度之差最多为1。 3、当插入新节点时,树会自我平衡。因此…...
一键安装 HaloDB 之 Ansible for Halo
↑ 关注“少安事务所”公众号,欢迎⭐收藏,不错过精彩内容~ 前倾回顾 前面介绍了“光环”数据库的基本情况和安装办法。 哈喽,国产数据库!Halo DB! 三步走,Halo DB 安装指引 以及 HaloDB 的 Oracle 和 MySQL 兼容模式: …...
el-table的上下筛选功能
el-table的sort-change事件可以监听到筛选的事件; 会返回prop属性和order排序的顺序; html: <el-table :data"tableData" border style"width: 100%" :cell-style"{ textAlign: center }"header-cell-c…...
【手撕面试题】Vue(高频知识点一)
每天10道题,100天后,搞定所有前端面试的高频知识点,加油!!!,在看文章的同时,希望不要直接看答案,先思考一下自己会不会,如果会,自己的答案是什么&…...
LabVIEW车轮动平衡检测系统
LabVIEW车轮动平衡检测系统 随着汽车行业的快速发展,车轮动平衡问题对乘坐舒适性、操控稳定性及安全性的影响日益凸显,成为了提高汽车性能的一个关键环节。传统的检测系统因精度低、成本高、操作复杂等问题,难以满足现代汽车行业的需求。开发…...
【Python爬虫--scrapy+selenium框架】超详细的Python爬虫scrapy+selenium框架学习笔记(保姆级别的,非常详细)
六,selenium 想要下载PDF或者md格式的笔记请点击以下链接获取 python爬虫学习笔记点击我获取 Scrapyselenium详细学习笔记点我获取 Python超详细的学习笔记共21万字点我获取 1,下载配置 ## 安装: pip install selenium## 它与其他库不同…...
【Linux】Linux环境基础开发工具_3
文章目录 四、Linux环境基础开发工具2. vim3. gcc和g动静态库的理解 未完待续 四、Linux环境基础开发工具 2. vim vim 怎么批量化注释呢?最简单的方法就是在注释开头和结尾输入 /* 或 */ 。当然也可以使用快捷键: Ctrl v 按 hjkl 光标移动进行区域选择…...
数字水印 | 图像噪声攻击(高斯/椒盐/泊松/斑点)
目录 Noise Attack1 高斯噪声(Gaussian Noise)2 椒盐噪声(Salt and Pepper Noise)3 泊松噪声(Poisson Noise)4 斑点噪声(Speckle Noise)5 完整代码 参考博客:Python…...
LeetCode-47 全排列Ⅱ
LeetCode-47 全排列Ⅱ 题目描述解题思路代码说明 题目描述 给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。 示例 : 输入:nums [1,1,2]输出: [[1,1,2], [1,2,1], [2,1,1]] b站题目解读讲的不好&…...
list 的实现
目录 list 结点类 结点类的构造函数 list的尾插尾删 list的头插头删 迭代器 运算符重载 --运算符重载 和! 运算符重载 * 和 -> 运算符重载 list 的insert list的erase list list实际上是一个带头双向循环链表,要实现list,则首先需要实现一个结点类,而一个结点需要…...
一个程序员的牢狱生涯(47)学法
星期一 学法 二铺不知道什么时候走到了我的身边,向我说道,这是二铺在我进来号子后主动过来和我说话。 我听到二铺这声突兀的说话后,抬起头。这时我才看到,除了二铺,还有六子、棍子都围在我的身边,看着我。虽然六子和棍子依旧一副‘吊儿郎当’的样子,但我从他们几个的眼神…...
微信小程序-页面导航
一、页面导航 页面导航指的是页面之间的相互跳转,例如:浏览器中实现页面导航的方式有如下两种: 1.<a>链接 2.location.href 二、小程序中实现页面导航的两种方式 1.声明式导航 在页面上声明一个<navigator>导航组件 通过点击…...
计算机网络- 特定服务类型(Type of Service, TOS) 服务质量(Quality of Service, QoS)
特定服务类型(Type of Service, TOS) 具有特定服务类型(Type of Service, TOS)的数据包是指在IP头部中包含特定TOS字段设置的数据包。TOS字段用于指示数据包的服务质量要求,如延迟、吞吐量、可靠性等。现代IP网络通常…...
2.6 Docker部署多个前端项目
2.6 Docker部署多个项目 三. 部署前端项目 1.将前端项目打包到同一目录下(tcm-ui) 2. 部署nginx容器 docker run --namenginx -p 9090:9090 -p 9091:9091 -d nginx3. 复制nginx.conf文件到主机目录 docker cp nginx:/etc/nginx/nginx.conf /root/ja…...
如何格式化只读U盘?
U盘只读无法格式化,该怎么处理?别担心!本文将向你提供一些实用方法,助你解决U盘写保护的难题。这些方法能有效帮助你解除U盘的只读状态,从而可以顺利进行格式化和其他操作。 不能格式化只读U盘 “我购买了一个U盘&…...
【并查集】专题练习
题目列表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 模板 836. 合并集合 - AcWing题库 #include<bits/stdc.h> using lllong long; //#define int ll const int N1e510,mod1e97; int n,m; int p[N],sz[N]; int find(int a) {if(p[a]!a) p[a]find(p[a]);return p[a…...
服装连锁店收银系统需要具备的五大功能
当今服装连锁店在市场竞争中需要拥有高效的收银系统来提升业务效率和顾客满意度。以下是服装连锁店收银系统需要具备的五大功能: 首先,完善的商品管理功能是至关重要的。这包括商品信息的录入、管理、更新和查询。收银系统应该能够快速而准确地识别商品&…...
IMU状态预积分代码实现 —— IMU状态预积分类
IMU状态预积分代码实现 —— IMU状态预积分类 实现IMU状态预积分类 实现IMU状态预积分类 首先,实现预积分自身的结构。一个预积分类应该存储一下数据: 预积分的观测量 △ R ~ i j , △ v ~ i j , △ p ~ i j \bigtriangleup \tilde{R} _{ij},\bigtrian…...
C语言编程:探索最小公倍数的奥秘
C语言编程:探索最小公倍数的奥秘 在编程的世界中,计算两个数的最小公倍数(LCM)是一个常见的数学问题。C语言作为一种基础且强大的编程语言,为我们提供了实现这一功能的工具。本文将从四个方面、五个方面、六个方面和七…...
Java设计模式-活动对象与访问者
活动对象 Java设计模式中,活动对象是指一个对象始终处于活动的状态,该对象包括一个线程安全的数据结构以及一个活跃的执行线程。 如上所示,ActiveCreature类的构造函数初始化一个线程安全的数据结构(阻塞队列)、初始化…...
用HAL库改写江科大的stm32入门-6-3 PWM驱动LED呼吸灯
接线图: 2 :实验目的: 利用pwm实现呼吸灯。 关键PWM定时器设置: 代码部分: int main(void) {/* USER CODE BEGIN 1 *//* USER CODE END 1 *//* MCU Configuration--------------------------------------------------------*…...
[数据集][目标检测]喝水检测数据集VOC+YOLO格式995张3类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):995 标注数量(xml文件个数):995 标注数量(txt文件个数):995 标注类别…...
【C++】开源:RabbitMQ安装与配置使用(SimpleAmqpClient)
😏★,:.☆( ̄▽ ̄)/$:.★ 😏 这篇文章主要介绍。 无专精则不能成,无涉猎则不能通。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下,下次更新不迷路…...
git使用流程与规范
原文网址:git代码提交流程与规范-CSDN博客 简介 本文git提交流程与规范是宝贵靠谱的经验,它能解决如下问题: 分支差距过大,导致合代码无数的冲突合完代码后发现代码丢失分支不清晰,无法追溯问题合代码耗时很长&…...
力扣 264. 丑数 II python AC
堆 from heapq import heappop, heappushclass Solution:def nthUglyNumber(self, n):q [1]vis {1}for _ in range(n - 1):now heappop(q)for i in [2, 3, 5]:if now * i not in vis:vis.add(now * i)heappush(q, now * i)return heappop(q)...
resetlogs强制拉库失败并使用备份system文件还原数据库故障处理---惜分飞
接手一个库,在open的过程中遭遇到ORA-600 2662错误 Sun May 26 10:15:54 2024 alter database open RESETLOGS RESETLOGS is being done without consistancy checks. This may result in a corrupted database. The database should be recreated. RESETLOGS after incomplete…...
解析Java中1000个常用类:Error类,你学会了吗?
在 Java 编程中,异常处理是一个至关重要的部分。Java 提供了丰富的异常处理机制,包括 Exception 和 Error。 本文将深入探讨 Error 类的功能、用法、实际应用中的注意事项,以及如何处理和预防这些错误。 什么是 Error 类? Error 类是 Java 中 Throwable 类的一个子类,用…...
【C++】——string模拟实现
前言 string的模拟实现其实就是增删改查,只不过加入了类的概念。 为了防止与std里面的string冲突,所以这里统一用String。 目录 前言 一 初始化和销毁 1.1 构造函数 1.2 析构函数 二 迭代器实现 三 容量大小及操作 四 运算符重载 4.1 bool…...
unity2D跑酷游戏
项目成果 项目网盘 导入资源包 放入Assets文件Assets资源文件 游戏流程分析 摄像机size调小,让图片占满屏幕 人跑本质,相对运动,图片无限向右滚动 图片720,缩小100倍第二个图片x为7.2每unit px100两张图片刚好挨着连贯 空对象Bg…...
OWASP top10--SQL注入(四、sqlmap安装及使用)
目录 sqlmap工具安装: 工具说明: 主要功能特性包括: 基本使用示例: 先下载python2.7.9版本 sqlmap运行 sqlmap工具使用 -u -r –-levelLEVEL扫描深度级别 --riskRISK 执行测试的风险 -threads 线程数 -batch-smart智能…...
Java基础入门day62
day62 AJAX 概念 AJAX: Asynchronous Javascript And XML AJAX是一种无需重新加载整个网页的情况下,能够更新部分网页的技术 AJAX是一种用于创建快速动态网页的技术 通过在后台与服务器进行少量数据交换,AJAX可以使网页实现异步更新 传统…...