当前位置: 首页 > news >正文

背包问题和单调栈

背包问题(动态规划)

动态五步曲

  • dp数组及下标索引的含义
  • 递推公式
  • dp数组如何初始化
  • 遍历顺序
  • 打印dp数组

01背包:n种物品,有一个,二维数组遍历顺序可以颠倒,(滚动数组)一维数组遍历顺序不可颠倒

完全背包:n种物品,有无限多个

多重背包:n种物品,数量各不相同

01背包

思路:

dp[i][j] ---> i是[0, i]之间的任意物品,放容量为j的背包中,所能得到的最大价值为dp[i][j],分不放物品和放物品的情况。
dp[j] ---> 容量为j的背包所能装的最大价值为dp[j],分为不放物品和放物品的情况,滚动数组倒序遍历,保证每一个物品只被添加一次。
// 01背包,滚动数组
for 物品for 背包(倒序 --> 每个物品只被添加一次 ),正序导致,物品被添加两次,不符合每个物品只能用一次

单调栈模版:

使用场景:比当前元素(左/右)大/小的数

// 输入 int[]  nums
int len = nums.length;
// 双端队列,既可以实现 栈 还可以实现 队列
Deque<Integer> stack = new LinkedList<>();		// 栈中存储的是元素的索引
for (int i = 0; i <len; i++) {// 递增栈if(nums[i] > nums[stack.peek()]) {// 如果需要存储可以提前 pop()while (!stack.isEmpty()  && nums[i] > nums[stack.peek()]) {// 当前索引下标 - 栈顶元素下标int res = i - stack.pop();stack.pop();}}stack.push(nums[i]);
}
return res;

相关文章:

背包问题和单调栈

背包问题&#xff08;动态规划&#xff09; 动态五步曲 dp数组及下标索引的含义递推公式dp数组如何初始化遍历顺序打印dp数组 01背包&#xff1a;n种物品&#xff0c;有一个,二维数组遍历顺序可以颠倒&#xff0c;&#xff08;滚动数组&#xff09;一维数组遍历顺序不可颠倒…...

Java | CompletableFuture详解

关注&#xff1a;CodingTechWork CompletableFuture 概述 介绍 CompletableFuture是 Java 8 引入的一个非常强大的类&#xff0c;属于 java.util.concurrent 包。它是用于异步编程的一个工具&#xff0c;可以帮助我们更方便地处理并发任务。与传统的线程池或 Future 对比&…...

【背包问题】二维费用的背包问题

目录 二维费用的背包问题详解 总结&#xff1a; 空间优化&#xff1a; 1. 状态定义 2. 状态转移方程 3. 初始化 4. 遍历顺序 5. 时间复杂度 例题 1&#xff0c;一和零 2&#xff0c;盈利计划 二维费用的背包问题详解 前面讲到的01背包中&#xff0c;对物品的限定条件…...

Golang 并发机制-5:详解syn包同步原语

并发性是现代软件开发的一个基本方面&#xff0c;Go&#xff08;也称为Golang&#xff09;为并发编程提供了一组健壮的工具。Go语言中用于管理并发性的重要包之一是“sync”包。在本文中&#xff0c;我们将概述“sync”包&#xff0c;并深入研究其最重要的同步原语之一&#xf…...

实验六 项目二 简易信号发生器的设计与实现 (HEU)

声明&#xff1a;代码部分使用了AI工具 实验六 综合考核 Quartus 18.0 FPGA 5CSXFC6D6F31C6N 1. 实验项目 要求利用硬件描述语言Verilog&#xff08;或VHDL&#xff09;、图形描述方式、IP核&#xff0c;结合数字系统设计方法&#xff0c;在Quartus开发环境下&#xff…...

如何用微信小程序写春联

​ 生活没有模板,只需心灯一盏。 如果笑能让你释然,那就开怀一笑;如果哭能让你减压,那就让泪水流下来。如果沉默是金,那就不用解释;如果放下能更好地前行,就别再扛着。 一、引入 Vant UI 1、通过 npm 安装 npm i @vant/weapp -S --production​​ 2、修改 app.json …...

LabVIEW无人机航线控制系统

介绍了一种无人机航线控制系统&#xff0c;该系统利用LabVIEW软件与MPU6050九轴传感器相结合&#xff0c;实现无人机飞行高度、速度、俯仰角和滚动角的实时监控。系统通过虚拟仪器技术&#xff0c;有效实现了数据的采集、处理及回放&#xff0c;极大提高了无人机航线的控制精度…...

C++哈希表深度解析:从原理到实现,全面掌握高效键值对存储

目录 一、核心组件与原理 1. 哈希函数&#xff08;Hash Function&#xff09; 2. 冲突解决&#xff08;Collision Resolution&#xff09; 3. 负载因子&#xff08;Load Factor&#xff09;与扩容 二、C实现&#xff1a;std::unordered_map 1. 模板参数 2. 关键操作与复…...

Vue.js组件开发-实现字母向上浮动

使用Vue实现字母向上浮动的效果 实现步骤 创建Vue项目&#xff1a;使用Vue CLI来创建一个新的Vue项目。定义组件结构&#xff1a;在组件的模板中&#xff0c;定义包含字母的元素。添加样式&#xff1a;使用CSS动画来实现字母向上浮动的效果。绑定动画类&#xff1a;在Vue组件…...

自研有限元软件与ANSYS精度对比-Bar2D2Node二维杆单元模型-四连杆实例

目录 1、四连杆工程实例以及手算求解 2、四连杆的自研有限元软件求解 2.1、选择单元类型 2.2、导入四连杆工程 2.3、节点坐标定义 2.4、单元连接关系、材料定义 2.5、约束定义 2.6、外载定义 2.7、矩阵求解 2.8、变形云图展示 2.9、节点位移 2.10、单元应力 2.11、…...

04树 + 堆 + 优先队列 + 图(D1_树(D11_伸展树))

目录 一、基本介绍 二、伸展操作 1. 左右情况的伸展 2. 左左情况的伸展 3. 右左情况的伸展 4. 右右情况的伸展 三、其它操作 1. 插入 2. 删除 四、代码实现 一、基本介绍 伸展树是一种二叉搜索树&#xff0c;伸展树也是一种平衡树&#xff0c;不过伸展树并不像AVL树那…...

c语言练习题【数据类型、递归、双向链表快速排序】

练习1&#xff1a;数据类型 请写出以下几个数据的数据类型 整数 a a 的地址 存放a的数组 b 存放a的地址的数组 b的地址 c的地址 指向 printf 函数的指针 d 存放 d的数组 整数 a 的类型 数据类型是 int a 的地址 数据类型是 int*&#xff08;指向 int 类型的指针&#xff09; …...

SliverAppBar的功能和用法

文章目录 1 概念介绍2 使用方法3 示例代码 我们在上一章回中介绍了SliverGrid组件相关的内容&#xff0c;本章回中将介绍SliverAppBar组件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1 概念介绍 我们在本章回中介绍的SliverAppBar和普通的AppBar类似&#xff0c;它们的…...

五、定时器实现呼吸灯

5.1 定时器与计数器简介 定时器是一种通过对内部时钟脉冲计数来测量时间间隔的模块。它的核心是一个递增或递减的寄存器&#xff08;计数器值&#xff09;。如果系统时钟为 1 MHz&#xff0c;定时器每 1 μs 计数一次。 计数器是一种对外部事件&#xff08;如脉冲信号&#xff…...

Elasticsearch的索引生命周期管理

目录 说明零、参考一、ILM的基本概念二、ILM的实践步骤Elasticsearch ILM策略中的“最小年龄”是如何计算的&#xff1f;如何监控和调整Elasticsearch ILM策略的性能&#xff1f; 1. **监控性能**使用/_cat/thread_pool API基本请求格式请求特定线程池的信息响应内容 2. **调整…...

【大模型理论篇】最近大火的DeepSeek-R1初探系列1

1. 背景介绍 这一整个春节&#xff0c;被DeepSeek-R1刷屏。各种铺天盖地的新闻以及老板发的相关信息&#xff0c;着实感受到DeepSeek-R1在国外出圈的震撼。 DeepSeek推出了新的推理模型&#xff1a;DeepSeek-R1-Zero 和 DeepSeek-R1。DeepSeek-R1-Zero 是一个在没有经过监督微调…...

【数据结构】(4) 线性表 List

一、什么是线性表 线性表就是 n 个相同类型元素的有限序列&#xff0c;每一个元素只有一个前驱和后继&#xff08;除了第一个和最后一个元素&#xff09;。 数据结构中&#xff0c;常见的线性表有&#xff1a;顺序表、链表、栈、队列。 二、什么是 List List 是 Java 中的线性…...

【C++ STL】vector容器详解:从入门到精通

【C STL】vector容器详解&#xff1a;从入门到精通 摘要&#xff1a;本文深入讲解C STL中vector容器的使用方法&#xff0c;涵盖常用函数、代码示例及注意事项&#xff0c;助你快速掌握动态数组的核心操作&#xff01; 一、vector概述 vector是C标准模板库&#xff08;STL&am…...

OpenAI推出Deep Research带给我们怎样的启示

OpenAI 又发新产品了&#xff0c;这次是面向深度研究领域的智能体产品 ——「Deep Research」&#xff0c;貌似被逼无奈的节奏… 在技术方面&#xff0c;Deep Research搭载了优化后o3模型并通过端到端强化学习在多个领域的复杂浏览和推理任务上进行了训练。因没有更多的技术暴露…...

洛谷[USACO08DEC] Patting Heads S

题目传送门 题目难度&#xff1a;普及/提高一 题面翻译 今天是贝茜的生日&#xff0c;为了庆祝自己的生日&#xff0c;贝茜邀你来玩一个游戏。 贝茜让 N N N ( 1 ≤ N ≤ 1 0 5 1\leq N\leq 10^5 1≤N≤105) 头奶牛坐成一个圈。除了 1 1 1 号与 N N N 号奶牛外&#xff0…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...