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

动态规划-背包问题——416.分割等和子集

1.题目解析

题目来源

416.分割等和子集——力扣

测试用例 

2.算法原理

1.状态表示

这里背包问题基本上和母题的思路大相径庭,母题请见 [模板]01.背包 ,这里的状态表示与装满背包的情况类似,第二个下标就是当选择的物品体积直接等于j时是否可以装入"背包",本题是求是否可以将一个数组分为大小相等的两部分,不妨变换思路,求出是否可以找一些数字的和等于该数组的一半,即

dp[i][j]:选择[1,i]区间的物品,此时总"体积"完全等于j时是否可以装入"背包"

2.状态转移方程

状态转移方程需要判断最后一个位置是否可以装入"背包",以此来判断此时位置的状态

1.当不选择当前位置:dp[i][j] = dp[i-1][j],不选择则"体积"不变,也就是j不变

2.选择当前位置:需要找到前面位置是否存在,也就是dp[i-1][j-nums[i-1]],注意判断j>=nums[i-1],不然就不能使用该位置的状态

3.初始化

开辟了虚拟位置,需要对虚拟位置进行初始化

4.填表顺序

从上到下,每一行从左到右

5.返回值 

返回最后一个位置的dp值

3.实战代码

class Solution {
public:bool canPartition(vector<int>& nums) {int m = nums.size();int sum = 0;for(auto e : nums){sum += e;}    int aim = sum / 2;if(sum % 2 == 1){return false;}vector<vector<bool>> dp(m+1,vector<bool>(aim+1));for(int i = 0;i <= m;i++){dp[i][0] = true;}for(int i = 1;i <= m;i++){for(int j = 1;j <= aim;j++){dp[i][j] = dp[i-1][j];if(j >= nums[i-1]){dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];}}}return dp[m][aim];}
};

代码解析 

代码优化 

 

相关文章:

动态规划-背包问题——416.分割等和子集

1.题目解析 题目来源 416.分割等和子集——力扣 测试用例 2.算法原理 1.状态表示 这里背包问题基本上和母题的思路大相径庭&#xff0c;母题请见 [模板]01.背包 &#xff0c;这里的状态表示与装满背包的情况类似&#xff0c;第二个下标就是当选择的物品体积直接等于j时是否可…...

Pr:视频过渡快速参考(合集 · 2025版)

Adobe Premiere Pro 自带七组约四十多个视频过渡 Video Transitions效果&#xff0c;包含不同风格和用途&#xff0c;可在两个剪辑之间创造平滑、自然的转场&#xff0c;用来丰富时间、地点或情绪的变化。恰当地应用过渡可让观众更好地理解故事或人物。 提示&#xff1a; 点击下…...

网络安全---安全见闻2

网络安全—安全见闻 拓宽视野不仅能够丰富我们的知识体系&#xff0c;也是自我提升和深造学习的重要途径&#xff01;&#xff01;&#xff01; 设备漏洞问题 操作系统漏洞 渗透测试视角&#xff1a;硬件设备上的操作系统可能存在各种漏洞&#xff0c;攻击者可以利用这些漏洞…...

解决因为TortoiseSVN未安装cmmand line client tools组件,导致idea无法使用svn更新、提交代码

一.错误信息 1.更新代码时&#xff1a;SVN: 更新错误 找不到要更新的版本管理目录。 2.提交代码&#xff1a;检测不到任何更新&#xff08;实际上有代码修改&#xff09;。 3.Cannot run program "svn"。 二.原因分析 在电脑上新安装的的客户端TortoiseSVN、ide…...

Ubuntu 20.04安装CUDA 11.0、cuDNN 8.0.5

不知道咋弄的ubuntu20.04电脑的cuda驱动丢了&#xff0c;无奈需装PyTorch环境&#xff0c;只有CUDA11.0以上版本才支持Ubuntu20.04&#xff0c;所以安装了CUDA11.0、cuDNN8.0.5 为防止频繁在浏览器检索对应的贴子&#xff0c;今天记录一下。 一. 驱动安装 为防止驱动安装后没…...

鸿蒙 APP 发布上架

证书创建与打包: https://developer.huawei.com/consumer/cn/doc/app/agc-help-releaseharmony-0000001933963166 不同环境多渠道打包: //todo 备案相关 一、除了发布应用商店以外,还有3个渠道,都适合小规模内测。 【1】开放式测试:发给指定白名单用户 【2】发布企业内…...

【C++笔记】C++三大特性之继承

【C笔记】C三大特性之继承 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;C笔记 文章目录 【C笔记】C三大特性之继承前言一.继承的概念及定义1.1 继承的概念1.2继承的定义1.3继承基类成员访问方式的变化1.4继承类模板 二.基类和派生类间的转…...

如何在CentOS 7上搭建SMB服务

如何在CentOS 7上搭建SMB服务 因项目测试需求&#xff0c;需要自行搭建SMB服务&#xff0c;**SMB&#xff08;Server Message Block&#xff09;**协议是一种常用的文件共享方式&#xff0c;它可以让不同操作系统之间共享文件、打印机等资源。本文将带你一步步搭建一个简单的S…...

linux详解,基本网络枚举

基本网络枚举 一、基本网络工具 ifconfig ifconfig是一个用于配置和显示网络接口信息的命令行工具。它可以显示网络接口的P地址、子网掩码、MC地址等信息&#xff0c;还可以用于启动、停止或配置网络接口。 ip ip也是用于查看和管理网络接口的命令。 它提供了比ifconfig更…...

5G智能对讲终端|北斗有源终端|北斗手持机|单兵|单北斗

在当今这个快速发展的数字化时代&#xff0c;5G技术的广泛应用正以前所未有的速度推动着各行各业的变革。作为这一技术浪潮中的重要一环&#xff0c;5G智能终端QM630D凭借其卓越的性能和多样化的功能&#xff0c;在林业、渔业、安保、电力、交通等多个领域展现出了巨大的应用潜…...

第七部分:2. STM32之ADC实验--AD多通道(AD采集三路传感器模块实验:光敏传感器、热敏传感器、反射式传感器附赠温湿度传感器教程)

这个多通道采用非扫描模式--单次转换模式 1.代码配置链路图 2. ADC的输入通道 3.ADC的非扫描模式的转换模式&#xff08;单次和连续&#xff09; 4.ADC的扫描模式的转换模式&#xff08;单次和连续&#xff09; 5.采集校准 代码实验&#xff1a; 代码部分&#xff1a; #inclu…...

js.零钱兑换

链接&#xff1a;322. 零钱兑换 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何…...

GitHub 上的开源项目推荐

GitHub 上的开源项目有成千上万&#xff0c;涵盖了从前端框架到数据科学、机器学习、系统工具等各个领域。不同的人根据兴趣和需求&#xff0c;可能会有不同的排名。不过&#xff0c;一些开源项目因为其广泛的应用、社区支持和技术创新&#xff0c;通常被认为是“最好”的开源项…...

实现Reactor反应堆模型:框架搭建

实现Reactor反应堆模型&#xff1a;框架搭建 Reactor模型是一种常用于处理大量并发I/O操作的设计模式&#xff0c;特别适用于服务器端的网络编程。该模型通过事件驱动的方式&#xff0c;将I/O操作的处理与具体的业务逻辑分离&#xff0c;从而提高系统的并发处理能力和响应速度…...

UE5 样条线组件(未完待续)

按点生成模型 按距离生成 spline mesh 可缩放spline mesh...

计算机网络常见面试题(一):TCP/IP五层模型、TCP三次握手、四次挥手,TCP传输可靠性保障、ARQ协议

文章目录 一、TCP/IP五层模型&#xff08;重要&#xff09;二、应用层常见的协议三、TCP与UDP3.1 TCP、UDP的区别&#xff08;重要&#xff09;3.2 运行于TCP、UDP上的协议3.3 TCP的三次握手、四次挥手3.3.1 TCP的三次握手3.3.2 TCP的四次挥手3.3.3 随机生成序列号的原因 四、T…...

sql速度优化多条合并为一条语句

在 SQL 中&#xff0c;结合 CASE 和 SUM 可以实现根据特定条件进行分组求和。在 ThinkPHP 中也可以使用类似的方式进行数据库查询操作。 例如&#xff0c;假设有一个销售数据表&#xff0c;包含字段 product_id &#xff08;产品 ID&#xff09;、 quantity &#xff08;销…...

用 PHP或Python加密字符串,用iOS解密

可以使用对称加密算法&#xff08;如 AES&#xff09;来加密和解密字符串。对称加密适合这种跨平台加密解密的需求&#xff0c;因为可以使用相同的密钥和算法在不同的编程语言和系统之间进行加密和解密。 下面展示如何使用 Python 或 PHP 进行加密&#xff0c;然后用 iOS (Swi…...

docker容器启动报错error creating overlay mount to /var/lib/docker/overlay2解决办法

背景&#xff1a;客户提供的机器用于部署服务&#xff0c;拿到发现docker是部署好的&#xff0c;但是selinux没有关闭&#xff0c;于是将/etc/selinux/config中的selinux设置成了disabled&#xff0c;但是并未重启&#xff0c;就继续部署服务了&#xff1b;结果几天后客户重启服…...

人工智能在智能家居中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 人工智能在智能家居中的应用 人工智能在智能家居中的应用 人工智能在智能家居中的应用 引言 人工智能概述 定义与原理 发展历程 …...

C# 操作XML

https://blog.csdn.net/2609_95039045/article/details/157469812?fromshareblogdetail&sharetypeblogdetail&sharerId157469812&sharereferPC&sharesourcem0_68206177&sharefromfrom_link 这个写的好 https://blog.csdn.net/lizhenxiqnmlgb/article/det…...

The Dark Art of Low-Light Enhancement: Why Retinex Models Don’t Need Handcrafted Priors Anymore

无先验约束的Retinex模型&#xff1a;PairLIE如何重塑低光增强技术范式 1. 低光增强的技术演进与当前挑战 在计算摄影领域&#xff0c;低光图像增强&#xff08;Low-light Image Enhancement, LIE&#xff09;一直是核心难题之一。传统方法主要依赖手工设计的先验知识&#xff…...

5分钟掌握ViGEmBus虚拟手柄驱动:Windows游戏控制器模拟终极指南

5分钟掌握ViGEmBus虚拟手柄驱动&#xff1a;Windows游戏控制器模拟终极指南 【免费下载链接】ViGEmBus Windows kernel-mode driver emulating well-known USB game controllers. 项目地址: https://gitcode.com/gh_mirrors/vi/ViGEmBus 想要在Windows电脑上体验专业级的…...

当Logo消失,品牌资产还剩多少?

这个问题问得直接——品牌费尽心思把Logo放大、放正、放在C位&#xff0c;可如果有一天消费者真的“看不见”它&#xff0c;品牌还剩下什么&#xff1f;答案取决于品牌建设的本质&#xff1a;是在做识别符号&#xff0c;还是在做价值沉淀。1. 认知资产&#xff1a;剩不下什么Lo…...

抖音视频批量下载:从零掌握双版本工具的完整实战指南

抖音视频批量下载&#xff1a;从零掌握双版本工具的完整实战指南 【免费下载链接】douyin-downloader 项目地址: https://gitcode.com/GitHub_Trending/do/douyin-downloader 在短视频内容日益丰富的今天&#xff0c;如何高效批量下载抖音视频成为许多内容创作者和研究…...

隔离变送器VS普通变送器:为什么你的PLC信号总受干扰?(实测XYS-5531抗干扰性能)

隔离变送器VS普通变送器&#xff1a;为什么你的PLC信号总受干扰&#xff1f;&#xff08;实测XYS-5531抗干扰性能&#xff09; 在工业自动化现场&#xff0c;信号干扰就像潜伏的"隐形杀手"——它不会直接摧毁设备&#xff0c;却能让控制系统频繁误动作、数据采集失真…...

从g2o优化框架看TEB算法:手撕局部路径规划的图优化实现

从g2o优化框架看TEB算法&#xff1a;手撕局部路径规划的图优化实现 在机器人导航领域&#xff0c;局部路径规划算法的性能直接决定了机器人在动态环境中的反应速度和避障能力。TEB&#xff08;Timed Elastic Band&#xff09;算法作为ROS生态中广泛采用的解决方案&#xff0c;其…...

Qwen3-VL多模态检索系统:跨模态搜索部署实战案例

Qwen3-VL多模态检索系统&#xff1a;跨模态搜索部署实战案例 用图文对话技术构建智能搜索系统&#xff0c;让AI看懂图片内容并精准回答你的问题 1. 项目介绍与环境准备 Qwen3-VL是阿里最新开源的视觉-语言模型&#xff0c;可以说是目前最强大的多模态AI系统之一。这个模型不仅…...

Qwen2.5-VL-7B-Instruct实战教程:如何将截图中的UI设计精准还原为可运行HTML+CSS

Qwen2.5-VL-7B-Instruct实战教程&#xff1a;如何将截图中的UI设计精准还原为可运行HTMLCSS 1. 工具简介与环境准备 Qwen2.5-VL-7B-Instruct是一个专门针对RTX 4090显卡优化的多模态大模型工具&#xff0c;它能看懂图片内容并生成相应的代码。想象一下&#xff0c;你只需要给…...

机器视觉中的坐标系转换:从像素到世界的无缝衔接

1. 机器视觉中的坐标系基础概念 第一次接触机器视觉时&#xff0c;最让我困惑的就是各种坐标系之间的关系。记得当时调试工业相机时&#xff0c;明明在图像上看到了目标物体&#xff0c;但机械臂就是抓不准位置。后来才发现&#xff0c;问题出在没有正确理解像素坐标系和世界坐…...