代码随想录-算法训练营day41(动态规划04:01背包,01背包滚动数组,分割等和子集)
第九章 动态规划part04● 01背包问题，你该了解这些！
● 01背包问题，你该了解这些！ 滚动数组
● 416. 分割等和子集 正式开始背包问题，背包问题还是挺难的，虽然大家可能看了很多背包问题模板代码，感觉挺简单，但基本理解的都不够深入。 如果是直接从来没听过背包问题，可以先看文字讲解慢慢了解 这是干什么的。如果做过背包类问题，可以先看视频，很多内容，是自己平时没有考虑到位的。 背包问题，力扣上没有原题，大家先了解理论，今天就安排一道具体题目。 详细布置 01背包问题 二维
https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html
视频讲解：https://www.bilibili.com/video/BV1cg411g7Y6 01背包问题 一维
https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html
视频讲解：https://www.bilibili.com/video/BV1BU4y177kY 416. 分割等和子集
本题是 01背包的应用类题目
https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
视频讲解：https://www.bilibili.com/video/BV1rt4y1N7jE
day41
01背包
方法一:二维数组
import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int bagweight = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i = 0; i < n; i++){weight[i] = sc.nextInt();}for(int i = 0; i<n; i++){value[i] = sc.nextInt();}//dp[i][j]表示0~i的物品放在容量j的背包的最大价值int[][] dp = new int[n][bagweight + 1];//初始化,dp[i][j]来自dp[i - 1][j]和dp[i - 1][j - weight[i]],所以初始化第1行和第1列for(int j = weight[0] ; j <= bagweight; j++){dp[0][j] = value[0];}for(int i = 1; i < n; i++){//对于二维数组,先遍历物品还是背包容量都可以,因为都来自正上方和左上方for(int j = 1; j <= bagweight; j++){if(j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);//注意可以更新压缩成一维数组,dp[i][j]都是由dp[i-1][j或者j-weight[i]]得来的}}System.out.println(dp[n - 1][bagweight]);}}
方法二:一维数组
//把[i]这个维度压缩了,滚动数组的时候从后往前遍历,因为每个数据都是需要上一行正上的数据和上一行左边的数据,在同一行操作的时候如果优先改了左边的数据,右边的数据更新会被影响import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int bagweight = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i = 0; i < n; i++){weight[i] = sc.nextInt();}for(int i = 0; i<n; i++){value[i] = sc.nextInt();}int[] dp = new int[bagweight + 1];for(int j = weight[0] ; j <= bagweight; j++){dp[j] = value[0];}for(int i = 1; i < n; i++){for(int j = bagweight; j >= weight[i]; j--){//if(j < weight[i]) dp[j] = dp[j];//判断多余了//else
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}System.out.println(dp[bagweight]);}}
分割等和子集
//相当于weight[i]和value[i]相同的bagweight = sum/2的01背包问题class Solution {public boolean canPartition(int[] nums) {if(nums == null || nums.length == 0) return false;int n = nums.length;int sum = 0;for(int num : nums) {sum += num;}if(sum % 2 != 0) return false;int target = sum / 2;int[] dp = new int[target + 1];for(int i = 0; i < n; i++) {for(int j = target; j >= nums[i]; j--) {//物品 i 的重量是 nums[i]，价值也是 nums[i]dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}//剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 20ms）//不用遍历完i,出现满足题意的装满的背包直接返回就行//为什么一定会在dp[target]处出现满足题意的背包,dp[target]有可能不正好是target,而是更大或者更小跳过正好是target的情况吗?//不可能,一个空间就是一个价值,target装满了最大就是target,只有可能是装满/不装满这两种情况,所以就是求最大价值的背包if(dp[target] == target)return true;}return dp[target] == target;}}
感谢大佬分享:
代码随想录-算法训练营day41【动态规划04：01背包问题-滚动数组、分割等和子集】_分隔等和子集 [1,5,11,5] 背包 滚动数组-CSDN博客
相关文章：
)
代码随想录-算法训练营day41(动态规划04:01背包,01背包滚动数组,分割等和子集)
第九章 动态规划part04● 01背包问题，你该了解这些！ ● 01背包问题，你该了解这些！ 滚动数组 ● 416. 分割等和子集 正式开始背包问题，背包问题还是挺难的，虽然大家可能看了很多背包问题模板代码…...
Vue Loader的作用
Vue Loader是一个专门用于处理Vue单文件组件（SFCs，即Single File Components）的webpack加载器（loader）。以下是Vue Loader的具体作用： 1、解析和转换Vue单文件组件 Vue Loader能够解析和转换.vue文件&…...
SRS 服务器入门：实时流媒体传输的理想选择
在当今视频流媒体需求爆炸式增长的时代，如何选择一款高效、稳定且功能强大的流媒体服务器成为了许多开发者和企业关注的焦点。而 SRS（Simple Realtime Server）作为一款开源的流媒体服务器，以其卓越的性能和灵活的功能，…...
4K高清壁纸网站推荐
1. Awesome Wallpapers 官网: https://4kwallpapers.com/ 主题: 创意、摄影、人物、动漫、绘画、视觉 分辨率: 4K Awesome Wallpapers 提供了丰富的高质量图片，分为通用、动漫、人物三大类，可以按屏幕比例和分辨率检索，满足你对壁纸的各种…...
如何保证数据库和缓存双写一致性？
数据库和缓存（redis）双写数据一致性问题再高并发的场景下，是一个很严重的问题，无论在工作中，还是面试，遇到的概率非常大，这里就聊一聊目前的常见解决方案以及最优方案。 常见方案 缓存的主要目…...
QT 多级嵌套结构体,遍历成员--半自动。＜模板+宏定义＞QTreeWidget树结构显示
Qt的QTreeWidget来显示嵌套结构体的成员，并以树形结构展示。 #include <QApplication> #include <QTreeWidget> #include <QTreeWidgetItem> #include <QString> #include <cstdint>// 假设这些是你的结构体定义 struct BaseMeterPa…...
《深入浅出HTTPS》读书笔记（17）：公开密钥算法
公开密钥算法（Public Key Cryptography），也称为非对称加密算法（Asymmetrical Cryptography）。 公开密钥算法的功能比较多，可以进行加密解密、密钥协商、数字签名。 【密钥是一对】 公开密钥算法的密钥是一对…...
React 中为什么不直接使用 requestIdleCallback?
首先看下 requestIdleCallback是什么？ 简介 requestIdleCallback 是一个在浏览器空闲时执行低优先级任务的 API。 定义与用途 requestIdleCallback 方法允许开发者在浏览器的空闲时段内调度函数的执行。这些函数通常用于执行非关键性的、低优先级的任务，…...
工作：SolidWorks从3D文件导出2D的DWG或DXF类型文件方法
工作：SolidWorks从3D文件导出2D的DWG或DXF类型文件方法 SolidWorks从3D文件导出2D的DWG或2D DXF类型文件方法（一）打开3D文件（二）从装配体到工程图（三）拖出想要的角度的图型（四&#…...
element-ui radio和checkbox禁用时不置灰还是原来不禁用时的样式
把要紧用的内容加上一个class"notEdit-page" z注意要在style里面写不能加上scoped /*//checkBox自定义禁用样式*//*//checkBox自定义禁用样式*/ .notEdit-page.el-checkbox__input.is-disabled.is-checked.el-checkbox__inner::after {border-color: #fff; } .notEdi…...
)
MySQL 8.0 安装与配置技术文档(Ubuntu22.04)
MySQL 8.0 安装与配置技术文档 目录 环境准备下载 MySQL 安装包检查是否已安装 MySQL彻底卸载 MySQL安装 MySQL配置 MySQL创建用户并允许外网访问修改 root 用户密码参考链接 1. 环境准备 确保系统为 Ubuntu 22.04，并安装了以下基础工具： sudo apt-ge…...
【Linux】Ubuntu中安装多个版本的gcc、g++编译器，并自由切换
1、安装 1.1 命令安装 使用命令直接安装： sudo apt install gcc-[版本号] sudo apt install g++-[版本号]例如： sudo apt install gcc-10 sudo apt install g++-10 sudo apt install gcc-9 sudo apt install g++-9 sudo apt install gcc-8 sudo apt install g++-81.2 源码…...
uni-app登录界面样式
非常简洁的登录、注册界面模板，使用uni-app编写，直接复制粘贴即可，无任何引用，全部公开。 废话不多说，代码如下： login.vue文件 <template><view class"screen"><view class"…...
如何在小米平板5上运行 deepin 23 ？
deepin 23 加入了 ARM64 支持，这里尝试将 deepin 系统刷入平板中，平常使用中，带个笔记本电脑有时候也会嫌比较麻烦，把 Linux 系统刷入平板中既满足了使用需要，又满足了轻便的需求。为什么不使用 Termux ？虽…...
Linux上的C语言编程实践
说明： 这是个人对该在Linux平台上的C语言学习网站笨办法学C上的每一个练习章节附加题的解析和回答 ex1: 在你的文本编辑器中打开ex1文件，随机修改或删除一部分，之后运行它看看发生了什么。 vim ex1.c打开 ex1.c 文件。假如我们删除 return 0…...
ubuntu中使用ffmpeg库进行api调用开发
一般情况下，熟悉了ffmpeg的命令行操作，把他当成一个工具来进行编解码啥的问题不大，不过如果要把功能集成进自己的软件中，还是要调用ffmpeg的api才行。 ffmpeg的源码和外带的模块有点太多了，直接用官网别人编译好的库就…...
基于yolov8的SAR影像目标检测系统，支持图像、视频和摄像实时检测【pytorch框架、python源码】
更多目标检测、图像分类识别、目标追踪等项目可看我主页其他文章 功能演示： 基于yolov8的SAR影像目标检测系统，支持图像、视频和摄像实时检测【pytorch框架、python源码】_哔哩哔哩_bilibili （一）简介 基于yolov8的SAR影像目标…...
【源码】Sharding-JDBC源码分析之SQL中读写分离动态策略、数据库发现规则及DatabaseDiscoverySQLRouter路由的原理
Sharding-JDBC系列 1、Sharding-JDBC分库分表的基本使用 2、Sharding-JDBC分库分表之SpringBoot分片策略 3、Sharding-JDBC分库分表之SpringBoot主从配置 4、SpringBoot集成Sharding-JDBC-5.3.0分库分表 5、SpringBoot集成Sharding-JDBC-5.3.0实现按月动态建表分表 6、【…...
服务器卸载安装的 Node.js
卸载安装的 Node.js 版本，具体步骤取决于你是通过包管理器（如 yum 或 dnf）安装的，还是通过 nvm (Node Version Manager) 安装的。以下是针对这两种情况的指南。 通过包管理器卸载 Node.js 如果你是通过 yum 或 dnf 安装的 Node.…...
一键图片提取表格导出为Excel文档工具体验
在日常工作中，我们经常会遇到需要将图片中的表格数据转换为可编辑的Excel文件的情况。这不仅能够提高工作效率，还能减少手动输入数据的错误。本文将介绍一款实用的工具，它能够帮助我们快速实现图片到Excel的转换，同时保持操作的简…...
SpringBoot异常处理
SpringBoot异常处理 一、认识异常 异常分类： Error: 代表编译和系统错误，不允许捕获Exception: 标准Java库的方法所激发的异常，包含运行异常Runtime_Exception和非运行异常 Non_RuntimeException 的子类Runtime_Exception: 运行时异常。No…...
在 OAuth 2.0 中，refreshToken（刷新令牌）存在的意义
在 OAuth 2.0 中，refreshToken（刷新令牌） 的主要目的是为了提升用户体验和安全性，同时确保访问令牌的有效性。以下是需要使用 refreshToken 的原因： 1. 访问令牌的有限生命周期 访问令牌（accessToken&…...
【Redis】壹 —— Redis 介绍
文章目录： 前言 一、认识Redis 1. Redis 用途 作为数据库 作为流引擎 二、服务端高并发分布式结构演变 1. 单机架构 2. 应用数据分离架构 3. 应用服务集群架构 4. 读写分离 / 主从分离架构 5. 冷热分离 —— 引入缓存 6. 分库分表 7. 微服务架构 8. …...
【html网页页面010】html+css制作茶品牌文创网页制作含视频元素（7页面附效果及源码）
茶主题品牌文创网页制作 🥤1、写在前面🍧2、涉及知识🌳3、网页效果完整效果(7页)：代码目录结构：page1、主页page2、精品包装page3、茶园一角page4、品牌地带page5、衍生品page6、联X我们page7、视频详情页 ἰ…...
【项目实战】基于python+爬虫的电影数据分析及可视化系统
注意：该项目只展示部分功能，如需了解，文末咨询即可。 本文目录 1.开发环境2 系统设计 2.1 设计背景2.2 设计内容 3 系统页面展示 3.1 用户页面3.2 后台页面3.3 功能展示视频 4 更多推荐5 部分功能代码 5.1 爬虫代码5.2 电影信息代码 1.开发环…...
K8S命令部署后端（流水线全自动化部署）
前言 本文为链接: 云效流水线k8s半自动部署java（保姆级）的补充,本文起初的目的是为了补充完善k8s流水线的全自动化部署,但是也适用于k8s的一键重启,因为使用k8s的web页面容易出现漏点的情况,因此也可以把代码保存为shell脚本,同样可以实现一键重启。关于…...
GPS北斗卫星授时服务器功能是什么？应用是什么？
GPS北斗卫星授时服务器功能是什么？应用是什么？ GPS北斗卫星授时服务器功能是什么？应用是什么？ 摘 要:首先对计算机网络时间同步相关技术进行了介绍,然后阐述了时间同步技术在现代计算机网络中的应用与发展,最后指出时间同步网络…...
学习笔记064——如何手动将jar包导入到maven本地库
文章目录 1、背景：2、方法 1、背景： 有时网络慢的情况， 本地maven库需要导入外部下载的jar包。 以便于在项目的pom文件中，直接写dependency写导入依赖。 2、方法 在Windows终端中，输入： mvn install:in…...
未来趋势系列 篇二：HBM题材解析和股票梳理
文章目录 系列文章HBM题材解析环氧塑封电镀液PSPI（光敏性聚酰亚胺）前驱体封装基板其他材料TSV技术封装测试股票梳理系列文章 未来趋势系列 篇一：AI题材解析和股票梳理 HBM HBM（High Bandwidth Memory，高带宽内存）是一种专为高效能运算设计的新兴高速内存接口技术。它通…...
网卡驱动测试
以下是网卡驱动不同测试类型的具体方法和命令： 1. 功能性测试 驱动加载/卸载测试： 方法：加载/卸载网卡驱动，观察日志是否报错。命令： modprobe <driver_name> # 加载驱动 rmmod <driver_name> # 卸载驱动…...
DDR的跨4K问题
参考视频：【深入理解FPGA底层逻辑】、4k边界和outsdanding_哔哩哔哩_bilibili 1、AXI4_FULL突发写一个字节是一个地址， 2、协议规定，把AXI4从机的地址区间从0进行到了4095....每4K进行一次分配 所以突发长度的计算如下： 另外AX…...
数据结构---栈（Stack）
1. 简介 栈（Stack）是计算机科学中的一种抽象数据类型，它遵循特定的操作顺序，即后进先出（Last In First Out，LIFO）。这意味着最后添加到栈中的元素将是第一个被移除的。栈的基本操作通常包括&am…...
【JavaWeb后端学习笔记】Java上传文件到阿里云对象存储服务
阿里云对象存储 1、创建阿里云对象存储节点2、上传文件2.1 修改项目配置文件2.2 定义一个Properties类获取配置信息2.3 准备一个alioss工具类2.4 创建注册类，将AliOssUtil 注册成Bean2.5 使用AliOssUtil 工具类上传文件2.6 注意事项 使用阿里云对象存储服务分为以下…...
Unity3D RPG战斗系统详解
前言 设计一个RPG（角色扮演游戏）的战斗系统是游戏开发中的关键环节，它决定了游戏的乐趣和挑战性。在Unity3D中，可以通过多种技术和工具来实现一个功能完善的战斗系统。以下是对RPG战斗系统的技术详解以及代码实现。 对惹&#x…...
Spark架构及运行流程
Spark架构图 Driver： 解析用户的应用程序代码，转化为作业(job)。创建SparkContext上下文对象，其负责与资源管理器(ClusterManager)通信，进行资源的申请、任务的分配和监控等。跟踪Executor的执行情况。可通过UI界面查询运行情况。…...
SpringBoot3整合MyBatis
一、MyBatis整合步骤: (1).导入依赖:在Spring Boot项目的构建文件(如pom.xml)中添加MyBatis和数据库驱动的相关依赖。例如，如果使用MySQL数据库，您需要添加MyBatis和MySQL驱动的依赖。 (2).配置数据源:在application.properties或application.yml中配置…...
【计网笔记】习题
物理层 不属于物理层接口规范定义范畴的是（C） A. 接口形状 B. 引脚功能 C. 物理地址 D. 信号电平 【2023-912】光网络只能通过导向型介质传播。（） 【2017-408】若信道在无噪声情况下的极限数据传输速率不小于信噪比为30dB条件下的…...
力扣56.合并区间
题目描述 题目链接56. 合并区间 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。 示例 1： …...
【oracle】大数据删除插入
文章目录 引言本文目标 Oracle大数据插入操作插入操作的场景和需求使用并行查询进行数据插入示例代码：创建新表并插入数据解释代码中的关键点 性能优化建议 Oracle大数据删除操作删除操作的场景和需求使用游标和批量处理进行数据删除示例代码：批量删除数…...
mysql 双1设置
MySQL 的"双1"设置通常指的是两个配置参数：innodb_flush_log_at_trx_commit 和 sync_binlog。这两个参数都与 MySQL 的数据安全和性能有关。 innodb_flush_log_at_trx_commit：这个参数控制了 InnoDB 引擎中事务日志的刷新频率。它有三个可能的…...
《C++ 赋能 K-Means 聚类算法：开启智能数据分类之旅》
在当今数字化浪潮汹涌澎湃的时代，人工智能无疑是引领科技变革的核心驱动力之一。而在人工智能的广袤天地中，数据分类与聚类作为挖掘数据内在价值、揭示数据潜在规律的关键技术手段，正发挥着前所未有的重要作用。K-Means 聚类算法，…...
用Python开发一个经典贪吃蛇小游戏
Python 是开发小游戏的绝佳工具，借助第三方库，如 pygame，我们可以快速开发一个经典的贪吃蛇游戏。本篇将介绍如何用 Python 实现一个完整的贪吃蛇小游戏。 一、游戏设计 1.1 游戏规则 玩家通过方向键控制贪吃蛇移动。贪吃蛇吃到食物后会变长，同时得分增加。如果贪吃蛇撞到…...
《大宋豪侠传》客户端源码 + 服务端源码 + 工具源码 + 资源，大小16.3G
《大宋豪侠传》客户端源码 服务端源码 工具源码 资源，大小16.3G 下载地址： 通过网盘分享的文件：【源码】《大宋豪侠传》客户端源码 服务端源码 工具源码 资源，大小16.3G 链接: https://pan.baidu.com/s/1lUf84LzXKB3iM7L-1P…...
使用vue-seamless-scroll实现echarts图表大屏滚动，出现空白间隔的解决方案
一、背景介绍 最近的业务开发需求，想要实现echarts图表大屏滚动，小编首先采用vue-seamless-scroll进行实现，结果发现第二屏出现空白间隔，尝试了多种解决方案均不生效，最终选择换一个方案。 二、封装的ScrollList组件…...
zsh配置
zsh配置 https://zhuanlan.zhihu.com/p/58073103 $ cat .zshrc If you come from bash you might have to change your $PATH. export PATH H O M E / b i n : / u s r / l o c a l / b i n : HOME/bin:/usr/local/bin: HOME/bin:/usr/local/bin:PATH Path to your oh-my-zs…...
Brain.js（八）：RNNTimeStep 实战教程 - 股票价格预测 - 实操需警慎
前置声明，个人浅度炒股，但计划将基金转入股市。然后 股市有风险，不是技术可以完全预测的，但是在无头绪的时候，用技术指标做个参考也不错。 本文涉及到的股票预测，只是代码简单示例，实操需警慎&a…...
Python+requests实现接口自动化测试
🍅 点击文末小卡片，免费获取软件测试全套资料，资料在手，涨薪更快 接口测试是测试系统组件间接口的一种测试。接口测试主要用于检测外部系统与系统之间以及内部各个子系统之间的交互点。测试的重点是要检查数据的交换，传…...
java------------常用API preiod duration 计算时间差
1，preiod 如果末天数比初天数小，需要进一位 package API;import java.time.LocalDate; import java.time.Period;public class preiod {public static void main(String[] args) {// 计算时间差// LocalDate获取对象其中的一个方法LocalDate d1 LocalD…...
Android水波纹效果
Android水波纹效果 需要到水波纹效果的场景还蛮少的。万一刚好你需要呢 一、思路： 自定义组件SpreadView 二、效果图： 看视频更直观点： Android轮子分享-水波纹效果 三、关键代码： public class SpreadView extends View {pr…...
yolov8 转华为昇腾om脚本
目录 yolov8 转华为昇腾 om脚本 测试ok 推理demo： yolov8 转华为昇腾 om脚本 测试ok import sys import osos.chdir(os.path.dirname(os.path.abspath(__file__)))import torchcurrent_dir = os.path.dirname(os.path.abspath(__file__))paths = [os.path.abspath(__file__)…...