代码随想录第42天|416. 分割等和子集

2024-04-22 04:20

本文主要是介绍代码随想录第42天|416. 分割等和子集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

416. 分割等和子集

416. 分割等和子集 - 力扣(LeetCode)

代码随想录 (programmercarl.com)

动态规划之背包问题,这个包能装满吗?| LeetCode:416.分割等和子集_哔哩哔哩_bilibili

给你一个 只包含正整数 的 非空 数组 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

找到集合里能够出现 sum / 2 的子集总和,就算是可以分割成两个相同元素和子集了。

该题中的元素只能使用一次,所以是01背包问题。

背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值。

动规五部曲:

1、确定dp数组以及下标的含义:dp[j]表示:容量为j的背包,所背物品的最大价值也为dp[j];

2、确定递推公式:dp[j]=max(dp[j] + dp[j]-weight[i]+value[i]),本题中:nums[i] = val[i], 所以:dp[j] = max(dp[j]+dp[j-nums[i]]+num[i])

3、dp数组如何初始化:dp[0] = 0;非0下标的元素初始为0;

4、确定遍历顺序:一维dp数组的循环中,物品在外,背包在内;

5、举例推导dp数组:

综合代码:

class Solution {public boolean canPartition(int[] nums) {if(nums == null || nums.length == 0) return false;int n = nums.length;int sum = 0;for(int num : nums) {sum += num;}//总和为奇数,不能平分if(sum % 2 != 0) return false;int target = sum / 2;int[] dp = new int[target + 1];for(int i = 0; i < n; i++) {for(int j = target; j >= nums[i]; j--) {//物品 i 的重量是 nums[i],其价值也是 nums[i]dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}//剪枝一下,每一次完成內層的for-loop,立即檢查是否dp[target] == target,優化時間複雜度(26ms -> 20ms)if(dp[target] == target)return true;}return dp[target] == target;}
}

这篇关于代码随想录第42天|416. 分割等和子集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/924807

相关文章

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能,来提高自己的 逻辑能力,熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd

生信代码入门:从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域,结合了生物学、计算机科学和统计学。随着高通量测序技术的发展,海量的生物数据需要通过编程来进行处理和分析。因此,掌握生信编程技能,成为每一个生物信息学研究者的必备能力。 生信代码入门,旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用

husky 工具配置代码检查工作流:提交代码至仓库前做代码检查

提示:这篇博客以我前两篇博客作为先修知识,请大家先去看看我前两篇博客 博客指路:前端 ESlint 代码规范及修复代码规范错误-CSDN博客前端 Vue3 项目开发—— ESLint & prettier 配置代码风格-CSDN博客 husky 工具配置代码检查工作流的作用 在工作中,我们经常需要将写好的代码提交至代码仓库 但是由于程序员疏忽而将不规范的代码提交至仓库,显然是不合理的 所

Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。 代码块 代码块语法遵循标准markdown代码,例如: using UnityEngine;using System.Collections;/// MouseLook rotates the transform based on the mouse delta./// Minimum and Maximum values can