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

力扣【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题解(背包问题)

首先我们可以求出数组和&#xff0c;当我们找到一个子集中元素的和为数组和的一半时&#xff0c;该就说明可以分割等和子集。 对于该问题我们可以转换成背包问题&#xff0c;求 数组里的元素 装入 数组和的一半大小的背包 能取得的最大值。 然后注意可以剪枝的地方。 代码&…...

2025年AI手机集中上市,三星Galaxy S25系列上市

2025年被认为是AI手机集中爆发的一年&#xff0c;各大厂商都会推出搭载人工智能的智能手机。三星Galaxy S25系列全球上市了。 三星Galaxy S25系列包含S25、S25和S25 Ultra三款机型&#xff0c;起售价为800美元&#xff08;约合人民币5800元&#xff09;。全系搭载骁龙8 Elite芯…...

为AI聊天工具添加一个知识系统 之79 详细设计之20 正则表达式 之7

本文要点 Q750、今天我们继续聊 本中的正则表达式。 在本项目&#xff08;为AI聊天工具添加一个知识系统&#xff09;中&#xff0c;将“正则表达式” 本来是计算机科学计算机科学的一个概念&#xff0c; 推广&#xff08;扩张&#xff09;到认知科学的“认知范畴”概念&#…...

理解PLT表和GOT表

1 简介 现代操作系统都是通过库来进行代码复用&#xff0c;降低开发成本提升系统整体效率。而库主要分为两种&#xff0c;一种是静态库&#xff0c;比如windows的.lib文件&#xff0c;macos的.a&#xff0c;linux的.a&#xff0c;另一种是动态库&#xff0c;比如windows的dll文…...

6 年没回老家过年了

今天是 2025 年的第一天&#xff0c;我们一家三口去了地坛庙会玩了会儿。 不是说过年的北京是空城吗&#xff1f;我愣是没抢到大年初一的门票&#xff0c;只好在咸鱼上溢价 40 买了两张票。 坐了一个小时的地坛终于到了&#xff0c;谁知迎来的是人山人海&#xff0c;同时小白牙…...

【原创改进】SCI级改进算法,一种多策略改进Alpha进化算法(IAE)

目录 1.前言2.CEC2017指标3.效果展示4.探索开发比5.定性分析6.附件材料7.代码获取 1.前言 本期推出一期原创改进——一种多策略改进Alpha进化算法&#xff08;IAE&#xff09;~ 选择CEC2017测试集低维&#xff08;30dim&#xff09;和高维&#xff08;100dim&#xff09;进行测…...

如何把一个python文件打包成一步一步安装的可执行程序

将一个 Python 文件打包成可执行程序&#xff08;如 .exe 文件&#xff09;&#xff0c;并实现一步一步的安装过程&#xff0c;通常需要以下步骤&#xff1a; 1. 将 Python 文件打包成可执行文件 使用工具将 Python 脚本打包成可执行文件&#xff08;如 .exe&#xff09;。常用…...

防火墙安全策略部署

目录&#xff1a; 一、实验拓扑&#xff1a; 二、实验要求&#xff1a; 三、需求分析&#xff1a; 四、详细设计&#xff1a; 五、实验步骤&#xff1a; 1.进行vlan划分&#xff1a; 2.IP配置&#xff1a; 3.云端服务配置&#xff1a; 4.划分子网&#xff1a; 5.防火墙…...

c++ map/multimap容器 学习笔记

1 map的基本概念 简介&#xff1a; map中所有的元素都是pair pair中第一个元素是key&#xff08;键&#xff09;&#xff0c;第二个元素是value&#xff08;值&#xff09; 所有元素都会根据元素的键值自动排序。本质&#xff1a; map/multimap 属于关联式容器&#xff0c;底…...

【解决方案】MuMu模拟器移植系统进度条卡住98%无法打开

之前在Vmware虚拟机里配置了mumu模拟器&#xff0c;现在想要移植到宿主机中 1、虚拟机中的MuMu模拟器12-1是目标系统&#xff0c;对应的目录如下 C:\Program Files\Netease\MuMu Player 12\vms\MuMuPlayer-12.0-1 2、Vmware-虚拟机-设置-选项&#xff0c;启用共享文件夹 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

桥接&#xff08;Bridging&#xff09;和NAT&#xff08;网络地址转换&#xff0c;Network Address Translation&#xff09;是网络中的两种不同技术&#xff0c;主要用于数据包的处理和转发。以下是它们的主要区别&#xff1a; 1. 工作原理 桥接&#xff1a; 桥接工作在数据链…...

人工智能 - 1

深度强化学习&#xff08;Deep Reinforcement Learning&#xff09; 图神经网络&#xff08;Graph Neural Networks, GNNs&#xff09; Transformer 一种深度学习模型 大语言模型&#xff08;Large Language Models, LLMs&#xff09; 人工智能 • 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)

题目来源 信息学奥赛一本通&#xff08;C版&#xff09;在线评测系统 题目描述 1144&#xff1a;单词翻转 时间限制: 1000 ms 内存限制: 65536 KB 提交数:60098 通过数: 26099 【题目描述】 输入一个句子(一行)&#xff0c;将句子中的每一个单词翻转后输出。 【输入…...

DeepSeek 模型全览:探索不同类别的模型

DeepSeek 是近年来备受关注的 AI 研究团队&#xff0c;推出了一系列先进的深度学习模型&#xff0c;涵盖了大语言模型&#xff08;LLM&#xff09;、代码生成模型、多模态模型等多个领域。本文将大概介绍 DeepSeek 旗下的不同类别的模型&#xff0c;帮助你更好地理解它们的特点…...

我的2024年年度总结

序言 在前不久&#xff08;应该是上周&#xff09;的博客之星入围赛中铩羽而归了。虽然心中颇为不甘&#xff0c;觉得这一年兢兢业业&#xff0c;每天都在发文章&#xff0c;不应该是这样的结果&#xff08;连前300名都进不了&#xff09;。但人不能总抱怨&#xff0c;总要向前…...

DeepSeek回答人不会干出超出视角之外的事

我本身是有着深度思考习惯的重度患者&#xff0c;当我遇到一个AI会深度思考的时候&#xff0c;我觉得找到了一个同类&#xff0c;是不是可以学习周伯通的左右手互博大法&#xff1f;下面我们拿着我的一点思考&#xff0c;让DeepSeek来再深度思考挖掘。 人不会干出超出视角之外的…...

前端知识速记—JS篇:null 与 undefined

前端知识速记—JS篇&#xff1a;null 与 undefined 什么是 null 和 undefined&#xff1f; 1. undefined 的含义 undefined 是 JavaScript 中默认的值&#xff0c;表示某个变量已被声明但尚未被赋值。当尝试访问一个未初始化的变量、函数没有返回值时&#xff0c;都会得到 u…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...