java分割等和子集(力扣Leetcode416)
分割等和子集
力扣原题链接
给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
01背包理论 (解决能不能装满背包的问题)
分析
- 分成两个子集,且元素和相同,可以看成将原来的所有元素加和除以2,这不就分成两个子集元素和相同了嘛。然后确定一个子集里的元素和是一半,另一个子集自动旧是另一半。
- 然后,我们可以将数组中的每个元素看作是一种物品,每个物品的价值(value)等于它的数值,而背包的容量(capacity)等于数组元素的和的一半。
- 我们的目标是尝试将这些物品放入背包中,使得背包的价值恰好等于容量的一半。
- 注意如果元素和本来就不能分成两份,那么直接返回·false·。

状态定义
我们定义一个二维的动态规划数组 dp,其中 dp[i][j] 表示在前 i 个物品中,能否选取一些物品使得它们的总和等于 j。
状态转移方程
在状态转移方程中,我们需要考虑当前物品是否放入背包中的两种情况:
- 如果不放入当前物品
nums[i - 1],则dp[i][j] = dp[i - 1][j]; - 如果放入当前物品
nums[i - 1],则dp[i][j] = dp[i - 1][j - nums[i - 1]]。
综合以上两种情况,状态转移方程为:
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]
初始化
我们需要对动态规划数组进行初始化,当没有物品或背包容量为0时。
Java解题
class Solution {public boolean canPartition(int[] nums) {int sum = 0;for(int a : nums){sum +=a;}if(sum % 2 !=0){return false;}int t = sum/2;int dp [] = new int[t+1];for(int i = 0 ;i < nums.length ;i ++){//遍历物品for (int j =t ; j >=nums[i] ;j--){//遍历背包 ! 倒序!dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);//背包最大价值的递推公式}}if(dp[t] == t ){//判断背包是否装满return true;}else{return false;}}
}
解题思路总结
通过以上步骤,我们可以分析出解决该问题的关键步骤,并用动态规划的思想进行解决。首先计算数组的总和,然后判断是否为偶数,如果不是偶数则返回false。接着根据动态规划的思想初始化dp数组,然后按照状态转移方程进行状态转移,最终返回dp数组的最后一个值。
相关文章:
java分割等和子集(力扣Leetcode416)
分割等和子集 力扣原题链接 给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] …...
383. 赎金信
给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以,返回 true ;否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 func canConstruct(ransomNote …...
【二】【单片机】有关独立按键的实验
自定义延时函数Delay 分别用Delay.c文件存储Delay函数。用Delay.h声明Delay函数。每次将这两个文件复制到工程中,直接使用。 //Delay.c void Delay(unsigned int xms) //11.0592MHz {while(xms--){unsigned char i, j;i 2;j 199;do{while (--j);}…...
AJAX踩坑指南(知识点补充)
JWT JSON Web Token是目前最为流行的跨域认证解决方案 如何获取:在使用JWT身份验证中,当用户使用其凭据成功登录时,将返回JSON Web Token(令牌) Token本质就是一个包含了信息的字符串 如何获取Token:登录成功之后,服务…...
备战蓝桥杯Day29 - 拼接最大数字问题
问题描述 有n个非负整数,将其按照字符串拼接的方式拼接为一个整数如何拼接可以使得得到的整数最大? 例: 32,94,128,1286,6,71可以拼接除的最大整数为 94716321286128。 问题思路 1.比较两个字符串的第一个数字,数值大的在前面,数值小的在…...
基于springboot的mysql实现读写分离
前言: 首先思考一个问题:在高并发的场景中,关于数据库都有哪些优化的手段?常用的有以下的实现方法:读写分离、加缓存、主从架构集群、分库分表等,在互联网应用中,大部分都是读多写少的场景,设置两个库,主库和读库,主库的职能是负责写,从库主要是负责读…...
Python爬虫之Scrapy框架系列(24)——分布式爬虫scrapy_redis完整实战【XXTop250完整爬取】
目录: 每篇前言:1.使用分布式爬取豆瓣电影信息(1)settings.py文件中的配置:(2)spider文件的更改:(3)items.py文件(两个项目一致!&…...
提升效率,稳定可靠:亚信安慧AntDB的企业价值
亚信安慧AntDB分布式数据库凭借平滑扩展、高可用性和低成本三大核心优势,在业界获得了极高的评价和认可。这些优点不仅为AntDB提供了巨大的市场发展潜力,也使其成为众多企业在数据管理上的首选解决方案。 AntDB的平滑扩展特性极大地提升了企业的灵活性和…...
洛谷入门——P1567 统计天数
统计天数 题目描述 炎热的夏日,KC 非常的不爽。他宁可忍受北极的寒冷,也不愿忍受厦门的夏天。最近,他开始研究天气的变化。他希望用研究的结果预测未来的天气。 经历千辛万苦,他收集了连续 N ( 1 ≤ N ≤ 1 0 6 ) N(1 \leq N …...
C++概述
目录 一、C关键字(63个) 二、C几个关键点: 三、C语言缺陷一:命名冲突 四、C新概念:命名空间(namespace) 五、命名空间的嵌套: 六、展开命名空间:(using …...
Linux学习笔记16 - 系统命令
1. Linux 常见系统管理命令 命令含义格式su切换用户su [选项] [用户名]ps显示系统由该用户运行的进程列表ps [选项]top动态显示系统中运行的程序(一般为每隔 5s)topkill输出特定的信号给指定 PID(进程号)的进程,并根据…...
读书笔记--阅读华为数据治理之旅有感
通过阅读华为的数据治理之旅,了解到华为公司作为高科技企业的引领者,在数据治理工作、数字化智能化转型方面的确有许许多多值得大家学习的地方,华为公司的业务范围广泛,市场竞争压力大,迫切需要用一些高效的手段来减轻员工的工作量,让员工各司其职,在各自承担的主营业务…...
网络安全协议基本问题
Http和Https协议的端口号: Http:80 Https:443 网络监听: 网络监听是一种监视网络状态、数据流程以及网络上信息传输的工具,它可以将网络界面设定成监听模式,并且可以截获网络上所传输的信息。但是网络监…...
面试(一)
一. 说一下进程和线程的区别? (1)进程是资源分配的最小单位,线程是CPU调度的最小单位。 (2)线程是进程的一部分,一个线程只能属于一个进程,一个进程可以有多个线程,但至少有一个线程。 (3)进程有自己独立地址空间&a…...
libVLC windows开发环境搭建
1.简介 LibVLC是一个强大的开源库,它构成了VLC媒体播放器的核心部分。 LibVLC提供了一系列的功能接口,使得VLC能够处理流媒体的接入、音频和视频输出、插件管理以及线程系统等核心任务。 跨平台性:VLC作为一个跨平台的多媒体播放器&#x…...
【Netty】Netty的使用和常用组件详解
目录 一、简述 1.1 什么是Netty 1.2 Netty 的优势 1.3 为什么不用 Netty5? 1.4 为什么 Netty 使用 NIO 而不是 AIO? 1.5 为什么不用 Mina? 二、第一个 Netty 程序 2.1 Bootstrap、EventLoop(Group) 、Channel 2.1.1 Bootstrap 2.1.…...
Legacy|电脑Windows系统如何迁移到新安装的硬盘?系统迁移详细教程!
前言 前面讲了很多很多关于安装系统、重装系统的教程。但唯独没有讲到电脑换了新的硬盘之后,怎么把旧系统迁移到新的硬盘上。 今天小白就来跟各位小伙伴详细唠唠: 开始之前需要把系统迁移的条件准备好,意思就是在WinPE系统下,可…...
Windows 11 安装 Scoop
[Windows 11 安装 Scoop](Windows 11 安装 Scoop) 0. 引言 Scoop 从命令行安装您熟悉和喜爱的程序,差异最小。 它的主要功能如下: 消除权限弹出窗口 隐藏 GUI 向导样式的安装程序 防止PATH污染安装大量程序 避免安装和卸载程序的意外副作用 自动查…...
新能源汽车小三电系统
小三电系统 新能源电动汽车的"小三电"系统,一般指车载充电机(OBC)、车载 DC/DC 变换器,和高压直流配电盒(PDU)。一辆纯电动汽车一般配备一台OBC 和一台车载 DC/DC 变换器。OBC将外部输入的交流电转化为直流电输出给电池,DC/DC衔接…...
面试问答示范
文章目录 请做个自我介绍您的学历是统招吗?可以在学信网查询吗是全日制吗是双证吗?请介绍一下你上家公司的情况。介绍一下你们公司的服务器架构(网络架构)。说说你在工作中处理过的最棘手的技术问题讲一讲上家公司做过的项目为什么…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !
我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...
