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

力扣:416. 分割等和子集(Java,动态规划:01背包问题)

目录

  • 题目描述:
  • 示例 1:
  • 示例 2:
  • 代码实现:

题目描述:

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2:

输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。

代码实现:

class Solution {public boolean canPartition(int[] nums) {if (nums.length == 1) {// 元素个数为1,直接为假return false;}int sum = 0;// 数组所有元素之和int max = 0;// 数组内最大元素for (int i = 0; i < nums.length; i++) {sum += nums[i];if (max < nums[i]) {max = nums[i];}}if (sum % 2 != 0) {// 如果元素之和为奇数,则必然不可能拆分为等和字迹return false;}int target = sum / 2;// 任一子集内元素之和if (max > target) {return false;// 如果最大值超过元素之和的一半,则必然不能等和}// 转化为01背包问题:nums[i]既是物品价值,也是物品重量int[] dp = new int[target + 1];// dp[j]表示容量为j的背包的最大价值:// 由于本题物品单价为1(价值=重量),所有尽可能装满背包即可// 采用一维数组压缩状态:滚动数组的方式for (int i = 0; i < nums.length; i++) {// 先遍历物品for (int j = target; j >= nums[i]; j--) {// 再倒序遍历背包:背包容量j要大于物品大小nums[i]dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);// 状态转移方程:两种情况的较大值// 1.背包不放物品nums[i],依然是上一轮背包状态dp[j]// 2.放物品nums[i],(背包j-当前物品重量nums[i])时的dp最大价值 + 当前放入物品价值nums[i]}}return dp[target] == target;// 题意求数组中是否存在一组和为target的元素集合// 转化成01背包问题:是否存在若干物品能够装入容量为target的背包}
}

相关文章:

力扣:416. 分割等和子集(Java,动态规划:01背包问题)

目录 题目描述&#xff1a;示例 1&#xff1a;示例 2&#xff1a;代码实现&#xff1a; 题目描述&#xff1a; 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集&#xff0c;使得两个子集的元素和相等。 示例 1&#xff1a; 输入&#…...

Vue进阶之Vue项目实战(一)

Vue项目实战 项目搭建初始化eslint版本约束版本约束eslint配置 stylelintcspellcz-githusky给拦截举个例子 zx 项目搭建 node版本&#xff1a;20.11.1 pnpm版本&#xff1a;9.0.4 初始化 vue3最新的脚手架 pnpm create vite byelide-demo --template vue-ts pnpm i pnpm dev…...

预告 | 飞凌嵌入式邀您共聚2024上海充换电展

第三届上海国际充电桩及换电站展览会&#xff08;CPSE&#xff09;&#xff0c;即将于5月22日~24日在上海汽车会展中心举行。届时&#xff0c;飞凌嵌入式将带来多款嵌入式核心板、开发板、充电桩TCU以及储能EMS网关产品&#xff0c;与来自全国的客户朋友及行业伙伴一同交流分享…...

vite 打包配置并部署到 nginx

添加配置 base&#xff1a;指项目在服务器上的相对路径&#xff0c;比如项目部署在 http://demo.dev/admin/ 上&#xff0c;那么你的基础路径就是 /admin/ 打包后生成的文件 部署到 nginx 访问部署地址&#xff0c;页面加载成功 参考文章&#xff1a;如何使用Vite打包和…...

ResponseHttp

文章目录 HTTP响应详解使用抓包查看响应报文协议内容 Response对象Response继承体系Response设置响应数据功能介绍Response请求重定向概述实现方式重定向特点 请求重定向和请求转发比较路径问题Response响应字符数据步骤实现 Response响应字节数据步骤实现 HTTP响应详解 使用抓…...

【题解】非对称之美(规律)

https://ac.nowcoder.com/acm/problem/214851 #include <iostream> #include <string> using namespace std; string s; int n; int fun() {// 1. 判断是否全都是相同字符bool flag false;for (int i 1; i < n; i) {if (s[i] ! s[0]){flag true;break;}}if…...

遇到如此反复的外贸客户,你可以这样做~

来源&#xff1a;宜选网&#xff0c;侵删 当你们遇到爽快的买家的时候&#xff0c;你是否有把握一定能把她拿下呢&#xff1f; 还是说即使客户很爽快&#xff0c;你也会耐心认真的沟通呢&#xff1f; 今天要和大家分享的这个买家&#xff0c;我本以为他是一个很爽快的买家&am…...

【数据库】简单SQL语句

已知某图书管理数据库有如下表格&#xff1a; 用户表user、部门表dept、角色表role、图书表book、图书分类表book_classify、图书借阅表book_borrow、还书表book_return、借阅预约表book_appoint、图书遗失表book_lose; 用户表user、部门表dept、角色表role、图书表book、图书…...

K邻算法:在风险传导中的创新应用与实践价值

01 前言 在当今工业领域&#xff0c;图思维方式与图数据技术的应用日益广泛&#xff0c;成为图数据探索、挖掘与应用的坚实基础。本文旨在分享嬴图团队在算法实践应用中的宝贵经验与深刻思考&#xff0c;不仅促进业界爱好者之间的交流&#xff0c;更期望从技术层面为企业在图数…...

【小白的大模型之路】基础篇:Transformer细节

基础篇&#xff1a;Transformer 引言模型基础架构原论文架构图EmbeddingPostional EncodingMulti-Head AttentionLayerNormEncoderDecoder其他 引言 此文作者本身对transformer有一些基础的了解,此处主要用于记录一些关于transformer模型的细节部分用于进一步理解其具体的实现机…...

Golang | Leetcode Golang题解之第73题矩阵置零

题目&#xff1a; 题解&#xff1a; func setZeroes(matrix [][]int) {n, m : len(matrix), len(matrix[0])col0 : falsefor _, r : range matrix {if r[0] 0 {col0 true}for j : 1; j < m; j {if r[j] 0 {r[0] 0matrix[0][j] 0}}}for i : n - 1; i > 0; i-- {for …...

JMeter性能压测脚本录制

第一步&#xff1a;电脑打开控制面板设置代理服务器 第二步&#xff1a;jmeter的测试计划添加一个HTTP&#xff08;S&#xff09;脚本记录器 在脚本记录器里配置好信息&#xff0c;然后保存为脚本文件&#xff08;.*表示限定&#xff09; 此方框内容为项目地址&#xff08;可改…...

缓存雪崩、缓存击穿、缓存穿透是什么、之间的区别及解决办法

缓存雪崩、缓存击穿、缓存穿透&#xff1a; 详细介绍看这篇文章&#xff0c;写得很好&#xff1a; 什么是缓存雪崩、缓存击穿、缓存穿透 下面是我自己总结的&#xff0c;比较简单清楚地展示了缓存雪崩、缓存击穿和缓存穿透的根本区别和相应的解决办法。强烈建议看完上述文章后…...

Pytorch张量广播

Pytorch 中的主要的数据结构包括标量、向量、矩阵、张量&#xff0c;同时支持数据之间的运算。在 Pytorch 中有一个张量广播的概念&#xff0c;就是要把小的放大&#xff0c;最后在一起做计算&#xff0c;并不是所有的张量都可以计算&#xff0c;规则如下 首先比较维度&#x…...

AI算法-高数2-导数定义和公式

P14 2.1 导数的定义(一):2.1 导数的定义_哔哩哔哩_bilibili 导数定义&#xff1a; 导数公式&#xff1a; P15 2.1 导数的定义(二)&#xff1a;2.1 导数的定义&#xff08;二&#xff09;_哔哩哔哩_bilibili [a,b]可导&#xff0c;a的端点&#xff1a;右可导&#xff0c;b端点&…...

Vitis HLS 学习笔记--AXI_STREAM_TO_MASTER

目录 1. 简介 2. 示例 2.1 示例功能介绍 2.2 示例代码 2.3 顶层函数解释 2.4 综合报告&#xff08;HW Interfaces&#xff09; 2.5 关于TKEEP和TSTRB 2.6 综合报告&#xff08;SW I/O Information&#xff09; 3. 总结 1. 简介 本文通过“<Examples>/Interface…...

WPF之可翻转面板

1&#xff0c;创建翻转面板的资源字典&#xff1a;FlippPanel.xaml。 无外观控件同样必须给样式指定类型&#xff08; <ControlTemplate TargetType"ss:FlipPanel">&#xff09;&#xff0c;相关详情参考&#xff1a;WPF之创建无外观控件-CSDN博客&#xff09…...

【深度学习】--slowfast视频理解数据集处理pipeline

官网指引&#xff1a; facebookresearch SlowFast &#xff1a;https://github.com/facebookresearch/SlowFast 进入dataset&#xff1a;https://github.com/facebookresearch/SlowFast/blob/main/slowfast/datasets/DATASET.md 这里面的东西需要通读&#xff0c;但是不要过于…...

ArcGIS10.2能用了10.2.2不行了(解决)

前两天我们的推文介绍了 ArcGIS10.2系列许可到期解决方案-CSDN博客文章浏览阅读2次。本文手机码字&#xff0c;不排版了。 昨晚&#xff08;2021\12\17&#xff09;12点后&#xff0c;收到很多学员反馈 ArcGIS10.2系列软件突然崩溃。更有的&#xff0c;今天全单位崩溃。​提示许…...

mysql查询表信息(表名、表结构、字段信息等)

MySQL中&#xff0c;您可以使用以下SQL查询数据库的表信息或者某个表中具体的信息&#xff0c;例如&#xff1a;字段、字段描述、索引等&#xff0c;以下为具体的SQL&#xff1a; 1、查询数据库所有表信息&#xff08;表名/表描述&#xff09; SELECTtable_name name,TABLE_C…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...