【leetcode100】分割等和子集
1、题目描述
给你一个 只包含正整数 的 非空 数组 nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和相等的子集。
2、初始思路
2.1 先验知识:0-1背包问题
2.1.1 0-1背包的描述:
有n件物品和⼀个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装⼊背包里物品价值总和最⼤。
使用动态规划的思路:
(1)确定dp数组及其含义
对于0-1背包问题,dp[i][j]/dp[i]表示背包能装下 j kg物品时,其最大价值。(dp[i][j]表示使用二维数组进行表示,dp[i]表示使用一维数组进行表示)
(2)递推公式
经过观察,递推公式应表示为:
dp[i][j] = max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]])
dp[j] = max(dp[j], value[i] + dp[j-weight[i]])
也就是,遍历物品,在物品能装进背包的情况下,考虑是否将其装进背包,其价值计算为当前物品的质量+背包减去当前物品重量所能装的最大价值。
(3)初始化dp数组
初始化数组,可将其价值均初始化0
m = len(weight)
dp = [[0] * (bagweight+1) for _ in range(m)]
dp = [0] * (bagweight+1)
(4)遍历顺序
当使用二维数组时,由于每个值都可以保存,因此可以从前向后进行遍历;
而当使用一维数组时,只能倒叙进行遍历,这样可以避免物品重复选择。此外,当使用一维数组时,只能先遍历物品,再遍历背包,因为要倒叙遍历,先遍历背包的话每个背包中将只能装一个物品。
2.1.2 代码
示例为:
(1)二维数组
class Solution:def bag(self, bagweight, weight, value):m = len(weight)dp = [[0] * (bagweight+1) for _ in range(m)]for i in range(m):for j in range(1, bagweight+1):if weight[i] > bagweight:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])return dp[m-1][bagweight]
solution = Solution()
bagweight = 4
weight = [1,3,4]
value = [15,20,30]
res = solution.bag(bagweight, weight, value)
print(res)
(2)一维数组
class Solution:def bag2(self, bagweight, weight, value):m = len(weight)dp = [0]*(bagweight+1)for i in range(m):for j in range(bagweight, weight[i]-1, -1):dp[j] = max(dp[j], dp[j-weight[i]]+value[i])return dp[bagweight]
solution = Solution()
bagweight = 4
weight = [1,3,4]
value = [15,20,30]
res = solution.bag2(bagweight, weight, value)
print(res)
2.2 思路
本题可以套用0-1背包的思路,也就是,将nums中的每个数的质量和价值都认为是其本身,背包容量为数组和的一半,这样,如果能找到dp[target] == target,那么表示nums可以被分为两个和相等的子集。
2.3 代码
class Solution:def canPartition(self, nums: List[int]) -> bool:target = sum(nums) // 2n = len(nums)if sum(nums) % 2 != 0:return Falsedp = [0] * (target+1)for i in range(n):for j in range(target, nums[i] - 1, -1):dp[j] = max(dp[j], nums[i] + dp[j - nums[i]])return dp[target] == target
3 优化算法
3.1 思路
本题主要的问题为能否找到子集,因此使用True/False 更自然且更高效。
3.2 代码
class Solution:def canPartition(self, nums: List[int]) -> bool:target = sum(nums) // 2n = len(nums)if sum(nums) % 2 != 0:return Falsedp = [False] * (target+1)dp[0] = Truefor i in range(n):for j in range(target, nums[i] - 1, -1):dp[j] = dp[j] or dp[j-nums[i]]return dp[target]
4 总结:0-1背包
使用gpt对0-1背包问题的重点进行了以下总结:
相关文章:
【leetcode100】分割等和子集
1、题目描述 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11…...
sed命令笔记250419
sed命令笔记250419 sed(Stream Editor)是 Linux/Unix 系统中强大的流编辑器,主要用于对文本进行过滤和转换(按行处理)。它支持正则表达式,适合处理文本替换、删除、插入等操作。以下是 sed 的详细解析&…...
LinearLayout 线性布局
目录 Android LinearLayout(线性布局)简单介绍与使用示例 一、效果介绍 二、布局文件(XML) 三、Java 代码 四、程序运行效果 五、总结 在 Android 移动应用开发中,LinearLayout(线性布局)…...
System.in 详解
System.in 详解 System.in 是 Java 提供的标准输入流(InputStream 类型),默认关联键盘输入,通常用于从控制台读取用户输入。由于它是字节流(InputStream),直接使用较麻烦,一般会配合…...
JAVA IO、BIO、NIO、AIO及零拷贝
概述 IO,常写作 I/O,是 Input/Output 的简称,是 Input/Output 的简称,即输入/输出。通常指数据在内部存储器(内存)和外部存储器(硬盘、优盘等)或其他周边设备之间的输入和输出。 目前有三种 IO 共存。分别是 BIO、NIO 和 AIO。 BIO 全称 Block-IO 是一种同步且阻塞的…...
AI预测3D新模型百十个定位预测+胆码预测+去和尾2025年4月19日第57弹
从今天开始,咱们还是暂时基于旧的模型进行预测,好了,废话不多说,按照老办法,重点8-9码定位,配合三胆下1或下2,杀1-2个和尾,再杀6-8个和值,可以做到100-300注左右。 (1)定…...
REST 架构详解:从概念到应用的全面剖析
REST(Representational State Transfer)即表述性状态转移,是一种用于构建网络应用程序的架构风格和设计理念,由计算机科学家罗伊・菲尔丁(Roy Fielding)在 2000 年提出。以下是关于它的详细介绍:…...
SICAR程序标准功能块 FB1512 “Robot_kuka_FB“
1、FB1512功能块截图 2、FB1512 功能块引脚功能定义 一、输入引脚 EN:使能输入,决定功能块是否执行。IDENTIFIER(WSTRING#"FW010_R01"):设备标识,指定关联的机器人设备。OPMODE_USER_INTERFACE_OUT:操作模式输入,定义机器人工作模式(如手动、自动),数据源…...
win安装软件
win安装软件 jdk安装 jdk安装 首先去官网下载适合系统版本的JDK,下载地址: http://www.oracle.com/technetwork/java/javase/downloads/index.html进入下载页面,如下图: 首先选择:Accept License Agreement单选按钮&…...
文本生成与采样策略 (Text Generation Sampling)
我们已经学习了如何构建和训练一个基于 Transformer Decoder-only 的语言模型。模型训练的目标是学习预测给定前缀下下一个 token 的概率分布。但是,训练完成后,我们如何利用这个模型来生成全新的、连贯的文本呢? 这就涉及到推理过程和采样策略。推理是模型投入实际使用、生…...
为什么 waitress 不支持 WebSocket?
waitress 是一个纯 Python 实现的 WSGI 服务器,主要用于生产环境部署 Python Web 应用。但它不支持 WebSocket 协议,因为它只实现了 WSGI 规范,而 WebSocket 协议需要 ASGI(Asynchronous Server Gateway Interface)支持…...
[C++] 高精度加法(作用 + 模板 + 例题)
高精度加法-目录 高精度加法用途高精度加法模板string转数位数组int 转数位数组(附加型知识点)高精度输出高精度加法函数大合集!!! 高精度加法用途 高精度加法通常用于加很大的数(真的很大, 超unsigned long long的那种). 高精度加法模板 注: 本篇数组下标0(x[0])存储的是该…...
python程序的流程
三大基本流程: 顺序结构、分支结构(又称为选择结构)、循环结构 分支结构又分为单分支、双分支、多分支 从键盘上输入一个数字,并输出奇数或偶数 #从键盘上输入一个数字,并输出奇数或偶数 nint(input("n ")…...
基于大模型的下肢静脉曲张全流程预测与诊疗方案研究报告
目录 一、引言 1.1 研究背景与意义 1.2 研究目的与创新点 1.3 研究方法与数据来源 二、下肢静脉曲张概述 2.1 定义与病理生理 2.2 风险因素与临床表现 2.3 诊断方法与现有治疗手段 三、大模型预测原理与构建 3.1 大模型技术简介 3.2 预测模型的数据收集与预处理 3.…...
Android 应用wifi direct连接通信实现
一. 打开Wi-Fi direct 1.必须启用Wi-Fi功能:在设备设置中开启Wi-Fi主开关(即使未连接路由器) 关闭冲突功能:若已开启「热点共享」或连接到其他Wi-Fi网络,需先关闭相关功能以避免硬件占. <!-- Wi-Fi Direct 核心权限…...
AI写代码工具分享:Cursor 高效使用攻略与实战秘籍
写在前面 在软件开发领域,效率和生产力是永恒的追求。集成开发环境(IDE)作为开发者的核心工具,其能力直接影响着开发速度和质量。近年来,人工智能(AI)的浪潮席卷了各个行业,编程领域也不例外。Cursor IDE 正是这股浪潮中的佼佼者,它以 AI-First 的理念,在广受欢迎的…...
关于viewpager常见的泄漏
在一个页面中 如果有用到tab,有需要进行fragment的切换,经常就看到了private var fragments arrayListOf<Fragment>()private fun initFragment() {arguments?.let {hopeToPosition it.getInt(IntentConstant.MAIN_PAGE_GO, 0)workoutType it.…...
vue3专题1------父组件中更改子组件的属性
理解 Vue 3 中父组件如何引用子组件的属性是一个很重要的概念。 这里涉及到 defineExpose 和 ref 这两个关键点。 方法:使用 defineExpose 在子组件中暴露属性,然后在父组件中使用 ref 获取子组件实例并访问暴露的属性。 下面我将详细解释这个过程&…...
代谢组数据分析(二十四):基于tidymass包从质谱原始数据到代谢物注释结果的实践指南
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍加载R包数据准备原始数据处理导入massDataset数据对象交互图数据探索更新样本表格信息峰分布情况缺失值情况数据清洗数据质量评估去除噪声代谢特征过滤立群样本填补缺失值数据标准化…...
Java使用javacv实现的多种音视频格式播放器
一、前言 最近写了一款图形界面版的音视频播放器,可以支持多种音视频格式的播放,比如MP4、avi、mkv、flv、MP3、ogg、wav等多种格式,非常好用,可以本地打开多种格式音视频。 二、实现 1.通过引入javacv相关依赖实现,如…...
csdn教程
hello,大家好,我是黑名单小羊,今天给大家分享一下csdn怎么换背景喵~ 成品: 首先,点击管理博文喵~ 然后,把任务栏往下翻喵~ 你就会看见博客设置,点击喵~ 再点击等级,如果你开通了 vip࿰…...
React 第三十三节 ReactRouter 中 useSearchParams 使用详解及注意事项
一、useSearchParams 定义 基本用法 定义:用于返回当前 URL 的 URLSearchParams 的元组和用于更新它们的函数。设置 search params 会导致导航。 import { useSearchParams } from react-router-dom export default function orderCenter() {const [searchParams,…...
@EnableAsync+@Async源码学习笔记之四
接上一篇,我们进入 AsyncAnnotationAdvisor 的分析,源码如下: package org.springframework.scheduling.annotation;import java.lang.annotation.Annotation; import java.util.HashSet; import java.util.LinkedHashSet; import java.util…...
【java实现+4种变体完整例子】排序算法中【快速排序】的详细解析,包含基础实现、常见变体的完整代码示例,以及各变体的对比表格
以下是快速排序的详细解析,包含基础实现、常见变体的完整代码示例,以及各变体的对比表格: 一、快速排序基础实现 原理 通过分治法选择一个基准元素(pivot),将数组分为两部分: 左边元素均小于…...
MAUI项目iOS应用以进 App Store 分发
目录 一.通过Visual Studio分发应用1. 登录Apple 开发者帐户到 Visual Studio2.创建分发证书和配置文件3. 分发应用4. 在App Store Connect 中创建应用程序记录5. 如果你想使用mac发布应用 一.通过Visual Studio分发应用 1. 登录Apple 开发者帐户到 Visual Studio 首先我们要…...
Linux——firewalld防火墙(笔记)
目录 一:Firewalld防火墙的概述 (1)firewalld简介 (2)firewalld&iptables的关系 (3)firewalld与iptables service的区别 1. 规则管理方式 2. 默认策略与设计逻辑 3. 配置文…...
SICAR标准功能块 FB1514 “Robot_request_FB”
1、功能块截图 2、引脚功能描述 输入引脚: EN:使能输入,控制功能块运行。PLANT_IDENTIFIER:工厂或设备标识符(如 #FWO10_RO1_SEGM_201),用于标识操作对象。OPMODE_USER:操作模式输入(用户模式)。INTERFACE_OUT:连接系统数据库的操作模式接口(SYSTEM_DB.OPmode[2].U…...
vue3 watch和watchEffect 的用法和区别
在 Vue 3 里,watch 和 watchEffect 都是用于响应式数据变化的 API,但它们在使用方法和应用场景上存在差异。下面详细介绍它们的用法和区别。 用法 watch watch 用于监听特定的响应式数据源,当数据源发生变化时,会执行相应的回调…...
Linux | I.MX6ULL 使用 Yocto 文件系统开发 QT
01 Yocto 文件系统默认支持了 QT,那么我们要怎么在 Yocto 文件系统来运行我们的 QT 程序呢?本章节我们就来学习上在 yocto 文件系统+Ubuntu 环境来开发 QT 程序。 注意,开发环境是基于“qtcreator-3.5.1”(Ubuntu16.04.6),库文件是Qt5.5.1 02 QT 安装 (1)首先我们…...
论文阅读:2024 ICLR Workshop. A STRONGREJECT for Empty Jailbreaks
总目录 大模型安全相关研究:https://blog.csdn.net/WhiffeYF/article/details/142132328 A STRONGREJECT for Empty Jailbreaks https://arxiv.org/pdf/2402.10260 https://github.com/dsbowen/strong_reject https://strong-reject.readthedocs.io/en/latest/ …...
数据结构实验7.2:二叉树的基本运算
文章目录 一,实验目的二,问题描述三,基本要求四,实验操作五,示例代码六,运行效果 一,实验目的 深入理解树与二叉树的基本概念,包括节点、度、层次、深度等,清晰区分二叉…...
关于一对多关系(即E-R图中1:n)中的界面展示优化和数据库设计
前言 一对多,是常见的数据库关系。在界面设计时,有时为了方便,就展示成逗号分割的字符串。例如:学生和爱好的界面。 存储 如果是简单存储,建立数据库:爱好,课程,存在一张表中。 但…...
Jenkins设置中文显示
1 安装插件 依次进入菜单: Jenkins -> Manage Jenkins -> Plugin Manager -> Avaliable 1.1 安装插件Locale plugin 1.2 安装插件Localization: Chinese(Simplified) 2 修改配置 点击菜单Manage Jenkins进入系统管理 点击菜单C…...
【MATLAB海洋专题】历史汇总
【MATLAB海洋专题】历史汇总 目录 01:海洋专题进阶教学 02:海洋数据处理 03:海洋数据下载 04:海洋配色 05:海洋专题基础教学 06: 其他基础画图 07:python 画海图专题 08:模式相关文件制作 01…...
【java实现+4种变体完整例子】排序算法中【归并排序】的详细解析,包含基础实现、常见变体的完整代码示例,以及各变体的对比表格
以下是归并排序的详细解析,包含基础实现、常见变体的完整代码示例,以及各变体的对比表格: 一、归并排序基础实现 原理 通过分治法将数组分为两半,递归排序子数组,最后合并有序子数组。 代码示例 public class Mer…...
深入理解前端安全:CSRF与XSS攻击详解
引言 在Web开发的世界里,安全性就像是房子的门锁。你可能觉得它不显眼,但一旦没了它,麻烦可就大了!本文将深入探讨两大前端安全威胁:CSRF(跨站请求伪造)和XSS(跨站脚本攻击…...
spring-batch批处理框架(2)
文章目录 八、作业控制8.1 作业启动8.1.1 SpringBoot 启动8.1.2 Spring 单元测试启动8.1.3 RESTful API 启动 8.2 作业停止方案1:Step 步骤监听器方式方案2:StepExecution停止标记 8.3 作业重启8.3.1 禁止重启8.3.2 限制重启次数8.3.3 无限重启 九、Item…...
[Java · 初窥门径] Java 注释符
🌟 想系统化学习 Java 编程?看看这个:[编程基础] Java 学习手册 0x01:Java 注释符简介 在编写程序时,为了使代码易于理解,通常会为代码加一些注释。Java 注释就是用通俗易懂的语言对代码进行描述或解释&a…...
linux下C++性能调优常用的工具
性能优化的常见流程 发现问题--->定位问题--->解决问题--->验证问题 发现问题的常见工具 1.定位内存问题 top指令,发现占用内存多的线程 asan 发现内存问题。 2.定位cpu问题 top指令,发现占用cpu多的进程,线程 一般对内存和…...
MinnowBoard MAX单板UEFI BIOS代码编译教程
此教程用于UEFI EDK2代码的研究,虽然EDK2框架代码开源,但是都是在模拟器上跑仿真,差点意思,搞过嵌入式大的应该有一个共识,是骡子是马,你得把板子点亮啊。MinnowBoard MAX单板是intel10多年前发布的软硬件全…...
真实波幅策略思路
该策略是一种基于ATR(Average True Range)指标的交易策略,主要用于期货市场中的日内交易。策略的核心思想是利用ATR指标来识别市场的波动范围,并结合均线过滤来确定买入和卖出的时机。 交易逻辑思维 1. 数据准备与初始化 - 集合竞…...
【每天一个知识点】模式识别
“模式识别”是一种从数据中识别出规律、结构或趋势的技术,它广泛应用于人工智能、机器学习、图像处理、语音识别、自然语言处理等领域。简单来说,就是让计算机学会“看出”数据中的规律,比如: 从图像中识别人脸(人脸识…...
Node.js 创建 HTTP 服务端
Node.js 创建 HTTP 服务端的用法总结,内容涵盖了 核心模块、基本用法、Express 简化用法、常见场景、错误处理、以及实用小贴士。 ✅ 一、Node.js 创建 HTTP 服务的方式 Node.js 使用内置的 http 模块即可快速创建一个 Web 服务,无需额外安装依赖。 ✅ …...
深入浅出伯努利分布:从 0‑1 随机世界到统计学习基石
深入浅出伯努利分布:从 0‑1 随机世界到统计学习基石 “当你能把一个问题拆解成一系列“是/否”答案时,伯努利分布就是第一块砖。” 目录 引言:伯努利分布为何如此重要?历史回顾:从赌博到信息论形式化定义与基本表示三…...
x-ui重新申请ssl证书失败
由于某些需要我们重新申请ssl证书,x-ui自动化脚本不能强制更新,根据x-ui仓库源码: https://github.com/vaxilu/x-ui/blob/main/x-ui.sh 在申请ssl证书的地方稍作修改,得到,运行下面的脚本就可以重新申请ssl证书&#…...
Python Requests 库:从安装到精通
摘要 本文详细介绍 Python Requests 库的安装与使用,通过常见示例让你轻松掌握。 一、引言 在当今的互联网时代,与各种 Web 服务进行交互是非常常见的需求。Python 作为一门功能强大且易于学习的编程语言,提供了许多用于网络请求的库&…...
No package docker-ce available问题的解决
安装docker时提示 rootk8s-node3 ~]# yum install -y docker-ce docker-ce-cli containerd.io Loaded plugins: fastestmirror Loading mirror speeds from cached hostfile * base: mirrors.aliyun.com * extras: mirrors.aliyun.com * updates: mirrors.aliyun.com No packag…...
SRS流媒体服务器
SRS流媒体服务器简介 SRS(Simple RTMP Server)是一个开源的流媒体服务器,主要用于直播和WebRTC场景。以下是关于SRS的关键信息: 主要特性 支持多种协议:RTMP、HTTP-FLV、HLS、WebRTC、SRT等低延迟:特别优化了WebRTC和HTTP-FLV的…...
【后端开发】Spring日志
文章目录 Spring日志日志作用日志测试日志信息日志级别日志配置配置日志级别日志持久化日志文件分割 注解的使用 Spring日志 日志作用 系统监控:可以通过日志记录这个系统的运行状态,对数据进行分析,设置不同的规则,超过阈值时进…...
Nginx 文件上传大小限制及 `client_max_body_size` 最大值详解
一、默认值与错误提示 默认值:client_max_body_size 1m; Nginx 默认允许的请求体最大为 1 MiB,超过该值会返回 413 Request Entity Too Large 错误。错误提示示例:HTTP/1.1 413 Request Entity Too Large Content-Type: text/html二、如何配…...