09_分割等和子集

简介: 09_分割等和子集

416. 分割等和子集

题目难易:中等

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

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1:

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

示例 2:

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

提示:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

【思路】

这道题目是要找是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。那么只要找到集合里能够出现 sum / 2 的子集总和,就算是可以分割成两个相同元素和子集了。

动态规划五部曲:

1、确定dp数组及其下标的含义

01背包找那个,dp[j]表示:容量为j的背包,所背的物品价值最大可以为dp[j]。

本题中每一个元素的数组既是重量,也是价值。

套到本题,dp[j]表示背包总容量(所能装的总重量)是j,放进物品后,背的最大重量为dp[j]。

那么如果背包容量为target, dp[target]就是装满背包之后的重量,所以当 dp[target] == target 的时候,背包就装满了。

2、确定递推公式

01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题,相当于背包里放入数值,那么物品i的重量是nums[i],其价值也是nums[i]。

所以递推公式:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

3、dp数组如何初始化

在01背包,一维dp如何初始化,已经讲过,

从dp[j]的定义来看,首先dp[0]一定是0。

如果题目给的价值都是正整数那么非0下标都初始化为0就可以了,如果题目给的价值有负数,那么非0下标就要初始化为负无穷。

这样才能让dp数组在递推的过程中取得最大的价值,而不是被初始值覆盖了。

本题题目中 只包含正整数的非空数组,所以非0下标的元素初始化为0就可以了。

代码如下:

//题中说:每个数组中的元素不会超过100,数组的大小不会超过200
//总和不会大于20000,背包最大只需要其中一般,所以10001大小就可以了
int[] dp = new dp[10001];

4、确定遍历顺序

如果使用一维dp数组,先遍历物品,在遍历背包。

代码如下:

//开始01背包
for (int i = 0; i < nums.size(); i++) {
  for (int j = target; j >= nums[i]; j--) {  //每一个元素一定是不可重复放入,所以从大到小遍历
  dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
  }
}

5、举例推导dp数组

dp[j]的数值一定是小于等于j的。

如果dp[j] == j 说明,集合中的子集总和正好可以凑成总和j,理解这一点很重要。

完整代码如下:

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;
    }
}
JAVA 复制 全屏

总结

这道题目就是一道01背包应用类的题目,需要我们拆解题目,然后套入01背包的场景。

01背包相对于本题,主要要理解,题目中物品是nums[i],重量是nums[i],价值也是nums[i],背包体积是sum/2。

看代码的话,就可以发现,基本就是按照01背包的写法来的。

相关文章
|
28天前
|
存储 弹性计算 大数据
阿里云服务器怎么样?介绍、费用、功能、优势、免费试用及问题解答FAQ
阿里云ECS是高性能、高可用的弹性云服务器,支持X86/ARM/GPU多种架构,提供e实例(99元/年)、u1、c9i等丰富规格;具备99.975%可用性、分钟级扩容、VPC隔离、快照镜像及5种计费模式,适配网站、AI、大数据等全场景。阿里云云服务器ECS官网:https://t.aliyun.com/U/AZBUsA
193 0
|
1月前
|
人工智能 自然语言处理 API
Token Plan是什么?有订阅的吗?使用Token真的省钱吗?
Token Plan是阿里云百炼推出的AI大模型订阅服务,支持个人版(39元起)和团队版,以统一Credits抵扣多模态模型及工具调用。用量匹配套餐则显著省钱,额度用尽自动停止,无超额费用。(239字)
|
5月前
|
SQL 人工智能 关系型数据库
【MySQL百日打怪升级第21天】InnoDB MVCC 机制详解 —— 快照读、当前读、Undo 链
本篇详解InnoDB MVCC机制:通过Read View(快照视图)与Undo版本链实现无锁并发控制,厘清快照读(普通SELECT)与当前读(UPDATE/FOR UPDATE)的本质区别,揭示RR/RC隔离级差异根源,并剖析长事务对性能的致命影响。
392 0
|
8月前
|
算法 NoSQL PHP
源码解析:社区团购系统中的三级分销算法、多端同步与城市代理机制
本文详解基于ThinkPHP 6与Uni-app的社区团购系统,支持微信/小程序/H5/APP多端同步、三级分销裂变、城市自动定位及代理商管理;采用Redis缓存、MySQL主从、Docker部署,兼顾高性能、高并发与数据私有化,助力创业者快速落地自有团购平台。(239字)
496 2
|
数据采集 监控 算法
原子钟的基本介绍
【10月更文挑战第7天】本文介绍原子钟是一种利用原子跃迁频率作为基准的高精度计时设备,广泛应用于通信、导航、科学研究等领域。铯原子钟是最精确的计时设备之一,基于铯133原子的超精细跃迁,频率为9,192,631,770 Hz。其关键部件包括铯束源、微波腔、磁态选择器、检测系统和反馈回路。原子钟在GPS、电信、金融市场等应用中至关重要,软件开发需考虑高精度时间同步、数据处理、硬件接口和性能监控。
2902 62
|
机器学习/深度学习 人工智能 自然语言处理
《一文读懂AI大模型:开启智能新时代的密码》
AI大模型是人工智能领域的重大飞跃,凭借Transformer架构和预训练-微调机制等核心技术,已在智能客服、内容创作、医疗诊断等领域广泛应用。它能处理多模态数据,大幅提升生产效率和生活质量。然而,大模型也面临可解释性、数据隐私和算力瓶颈等挑战。未来,随着技术进步,AI大模型将更加通用化和智能化,推动社会变革,创造更多奇迹。
1158 11
|
存储 缓存 监控
后端性能优化:从理论到实践
在数字化时代,后端服务的性能直接影响着用户体验和业务效率。本文将深入探讨后端性能优化的重要性,分析常见的性能瓶颈,并提出一系列切实可行的优化策略。我们将从代码层面、数据库管理、缓存机制以及系统架构设计等多个维度出发,结合具体案例,详细阐述如何通过技术手段提升后端服务的响应速度和处理能力。此外,文章还将介绍一些先进的监控工具和方法,帮助开发者及时发现并解决性能问题。无论是初创公司还是大型企业,本文提供的策略都有助于构建更加高效、稳定的后端服务体系。
765 3
|
搜索推荐 数据挖掘 BI
问卷调查软件精选,效能与易用双赢
本文推荐了四款问卷调查软件:ZohoSurvey、SurveyMonkey、GoogleForms和Typeform。ZohoSurvey功能全面,性价比高,适合中小企业和个人;SurveyMonkey功能强大,适合大型企业和科研机构;GoogleForms免费易用,适合预算有限的用户;Typeform注重用户体验,适合需要高参与率的调查。选择时需综合考虑功能、易用性和品牌信任度等因素。
679 2
|
测试技术 程序员 C#
《黑神话:悟空》:从Unity到UE4 —— 游戏引擎迁移的挑战与机遇
【8月更文第26天】近年来,游戏行业的发展突飞猛进,特别是在图形表现力和技术实现上。《黑神话:悟空》是一款备受期待的动作角色扮演游戏,该游戏在早期开发阶段使用了Unity引擎,但为了追求更高的视觉质量和更强大的技术能力,开发团队决定将其迁移到Unreal Engine 4 (UE4)。本文将探讨这一迁移过程中的技术挑战与机遇。
1766 1
|
SQL 监控 算法
为Go应用无侵入地添加任意代码
这篇文章旨在提供技术深度和实践指南,帮助开发者理解并应用这项创新技术来提高Golang应用的监控与服务治理能力。在接下来的部分,我们将通过一些实际案例,进一步展示如何在不同场景中应用这项技术,提供更多实践启示。