力扣【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…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...

分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...

2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版
1.题目描述 2.思路 当前的元素可以重复使用。 (1)确定回溯算法函数的参数和返回值(一般是void类型) (2)因为是用递归实现的,所以我们要确定终止条件 (3)单层搜索逻辑 二…...