力扣【416. 分割等和子集】详细Java题解(背包问题)
首先我们可以求出数组和,当我们找到一个子集中元素的和为数组和的一半时,该就说明可以分割等和子集。
对于该问题我们可以转换成背包问题,求 数组里的元素 装入 数组和的一半大小的背包 能取得的最大值。
然后注意可以剪枝的地方。
代码:
class Solution {public boolean canPartition(int[] nums) {//计算数组的和int sum =0;for(int num:nums) sum += num;if(sum%2 != 0) return false; //如果和为奇数,那就不符合sum /= 2;int[][] dp = new int[nums.length+1][sum+1]; //dp[i][j]表示遍历到前i个物品时,j容量背包能转的最大值//第0行就是还没有物品加入计算,初始化为0for(int i=0;i<sum+1;i++){dp[0][i] = 0; }//开始动规计算for(int i=1;i<=nums.length;i++){for(int j=1;j<=sum;j++){if(nums[i-1] <= j) dp[i][j] = Math.max(nums[i-1] + dp[i-1][j-nums[i-1]],dp[i-1][j]);else dp[i][j] = dp[i-1][j];}if(dp[i][sum] == sum) return true; //剪枝}//结果判断if(dp[nums.length][sum] == sum){return true;}return false;}
}
不过我们其实可以用一维数组来做,因为我们的每次迭代其实只用到了dp数组的上一行。那我们可以用一个数组来进行滚动,不过遍历顺序得从后往前,因为我们迭代后面的物品时需要用到前面物品的值,且当容量大于当前遍历的物品时才迭代。
这样我们的代码更简洁且时间复杂度和空间复杂度都有改善。
class Solution {public boolean canPartition(int[] nums) {//计算数组的和int sum =0;for(int num:nums) sum += num;if(sum%2 != 0) return false; //如果和为奇数,那就不符合sum /= 2;int[] dp = new int[sum+1]; //第0行就是还没有物品加入计算,初始化为0for(int i=0;i<sum+1;i++){dp[i] = 0; }//开始动规计算for(int i=1;i<=nums.length;i++){for(int j=sum;j>=nums[i-1];j--){dp[j] = Math.max(nums[i-1] + dp[j-nums[i-1]],dp[j]);if(j==sum && dp[j] == sum) return true; //剪枝}}return false;}
}
相关文章:
力扣【416. 分割等和子集】详细Java题解(背包问题)
首先我们可以求出数组和,当我们找到一个子集中元素的和为数组和的一半时,该就说明可以分割等和子集。 对于该问题我们可以转换成背包问题,求 数组里的元素 装入 数组和的一半大小的背包 能取得的最大值。 然后注意可以剪枝的地方。 代码&…...
2025年AI手机集中上市,三星Galaxy S25系列上市
2025年被认为是AI手机集中爆发的一年,各大厂商都会推出搭载人工智能的智能手机。三星Galaxy S25系列全球上市了。 三星Galaxy S25系列包含S25、S25和S25 Ultra三款机型,起售价为800美元(约合人民币5800元)。全系搭载骁龙8 Elite芯…...
为AI聊天工具添加一个知识系统 之79 详细设计之20 正则表达式 之7
本文要点 Q750、今天我们继续聊 本中的正则表达式。 在本项目(为AI聊天工具添加一个知识系统)中,将“正则表达式” 本来是计算机科学计算机科学的一个概念, 推广(扩张)到认知科学的“认知范畴”概念&#…...
理解PLT表和GOT表
1 简介 现代操作系统都是通过库来进行代码复用,降低开发成本提升系统整体效率。而库主要分为两种,一种是静态库,比如windows的.lib文件,macos的.a,linux的.a,另一种是动态库,比如windows的dll文…...
6 年没回老家过年了
今天是 2025 年的第一天,我们一家三口去了地坛庙会玩了会儿。 不是说过年的北京是空城吗?我愣是没抢到大年初一的门票,只好在咸鱼上溢价 40 买了两张票。 坐了一个小时的地坛终于到了,谁知迎来的是人山人海,同时小白牙…...
【原创改进】SCI级改进算法,一种多策略改进Alpha进化算法(IAE)
目录 1.前言2.CEC2017指标3.效果展示4.探索开发比5.定性分析6.附件材料7.代码获取 1.前言 本期推出一期原创改进——一种多策略改进Alpha进化算法(IAE)~ 选择CEC2017测试集低维(30dim)和高维(100dim)进行测…...
如何把一个python文件打包成一步一步安装的可执行程序
将一个 Python 文件打包成可执行程序(如 .exe 文件),并实现一步一步的安装过程,通常需要以下步骤: 1. 将 Python 文件打包成可执行文件 使用工具将 Python 脚本打包成可执行文件(如 .exe)。常用…...
防火墙安全策略部署
目录: 一、实验拓扑: 二、实验要求: 三、需求分析: 四、详细设计: 五、实验步骤: 1.进行vlan划分: 2.IP配置: 3.云端服务配置: 4.划分子网: 5.防火墙…...
c++ map/multimap容器 学习笔记
1 map的基本概念 简介: map中所有的元素都是pair pair中第一个元素是key(键),第二个元素是value(值) 所有元素都会根据元素的键值自动排序。本质: map/multimap 属于关联式容器,底…...
【解决方案】MuMu模拟器移植系统进度条卡住98%无法打开
之前在Vmware虚拟机里配置了mumu模拟器,现在想要移植到宿主机中 1、虚拟机中的MuMu模拟器12-1是目标系统,对应的目录如下 C:\Program Files\Netease\MuMu Player 12\vms\MuMuPlayer-12.0-1 2、Vmware-虚拟机-设置-选项,启用共享文件夹 3、复…...
日志收集Day007
1.配置ES集群TLS认证: (1)elk101节点生成证书文件 cd /usr/share/elasticsearch ./bin/elasticsearch-certutil cert -out config/elastic-certificates.p12 -pass "" --days 3650 (2)elk101节点为证书文件修改属主和属组 chown elasticsearch:elasticsearch con…...
虚拟机里网络设置-桥接与NAT
桥接(Bridging)和NAT(网络地址转换,Network Address Translation)是网络中的两种不同技术,主要用于数据包的处理和转发。以下是它们的主要区别: 1. 工作原理 桥接: 桥接工作在数据链…...
人工智能 - 1
深度强化学习(Deep Reinforcement Learning) 图神经网络(Graph Neural Networks, GNNs) Transformer 一种深度学习模型 大语言模型(Large Language Models, LLMs) 人工智能 • Marvin Minsky 将其定义…...
小程序-基础加强-自定义组件
前言 这次讲自定义组件 1. 准备今天要用到的项目 2. 初步创建并使用自定义组件 这样就成功在home中引入了test组件 在json中引用了这个组件才能用这个组件 现在我们来实现全局引用组件 在app.json这样使用就可以了 3. 自定义组件的样式 发现页面里面的文本和组件里面的文…...
Kafka 压缩算法详细介绍
文章目录 一 、Kafka 压缩算法概述二、Kafka 压缩的作用2.1 降低网络带宽消耗2.2 提高 Kafka 生产者和消费者吞吐量2.3 减少 Kafka 磁盘存储占用2.4 减少 Kafka Broker 负载2.5 降低跨数据中心同步成本 三、Kafka 压缩的原理3.1 Kafka 压缩的基本原理3.2. Kafka 压缩的工作流程…...
单词翻转(信息学奥赛一本通1144)
题目来源 信息学奥赛一本通(C版)在线评测系统 题目描述 1144:单词翻转 时间限制: 1000 ms 内存限制: 65536 KB 提交数:60098 通过数: 26099 【题目描述】 输入一个句子(一行),将句子中的每一个单词翻转后输出。 【输入…...
DeepSeek 模型全览:探索不同类别的模型
DeepSeek 是近年来备受关注的 AI 研究团队,推出了一系列先进的深度学习模型,涵盖了大语言模型(LLM)、代码生成模型、多模态模型等多个领域。本文将大概介绍 DeepSeek 旗下的不同类别的模型,帮助你更好地理解它们的特点…...
我的2024年年度总结
序言 在前不久(应该是上周)的博客之星入围赛中铩羽而归了。虽然心中颇为不甘,觉得这一年兢兢业业,每天都在发文章,不应该是这样的结果(连前300名都进不了)。但人不能总抱怨,总要向前…...
DeepSeek回答人不会干出超出视角之外的事
我本身是有着深度思考习惯的重度患者,当我遇到一个AI会深度思考的时候,我觉得找到了一个同类,是不是可以学习周伯通的左右手互博大法?下面我们拿着我的一点思考,让DeepSeek来再深度思考挖掘。 人不会干出超出视角之外的…...
前端知识速记—JS篇:null 与 undefined
前端知识速记—JS篇:null 与 undefined 什么是 null 和 undefined? 1. undefined 的含义 undefined 是 JavaScript 中默认的值,表示某个变量已被声明但尚未被赋值。当尝试访问一个未初始化的变量、函数没有返回值时,都会得到 u…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
