【数据结构和算法】01 背包的应用
🎈 作者:
🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
🎈 关注专栏:
优质好文持续更新中……🚀🚀🚀🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
目录
「背包问题」在算法中经常用到,尤其是「01 背包」,下面就来看一下 「01 背包」的应用。
🍓一、题目描述
给定一个只包含正整数的非空数组 nums 。请判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
🔶🔶🔶🔶🔶 我是华丽的分割线 🔶🔶🔶🔶🔶
🍓二、测试样例
🥝2.1 样例 1
输入:nums = [1,5,11,5]
输出:true
说明:数组可以分割成 [1, 5, 5] 和 [11] ,两者之和都为 11。
🥝2.2 样例 2
输入:nums = [1,2,3,5]
输出:false
说明:数组之和为 11,显然不能分割成两个元素和相等的子集。
🔶🔶🔶🔶🔶 我是华丽的分割线 🔶🔶🔶🔶🔶
🍓三、算法思路
本题可以将题意简化为:
判断正整数数组 nums 是否存在一个子集,这个子集的和为 nums 数组中所有值和的一半。
题意转化后就好解题了,就是在 nums 中挑选一些数字,这些数字之和正好组成一个给定的数,很明显是一个「背包问题」,因为物品(nums 中的数字)不能重复选择,所以是一个 「背包」问题。
「01 背包」问题可以 关注专栏
注意:这里要求背包正好装满(挑选的子集中的数字之和正好为 nums 数组所有数和的一半)。
🔶🔶🔶🔶🔶 我是华丽的分割线 🔶🔶🔶🔶🔶
🍓四、代码实现
其中,sum 为计算 nums 数组中的所有数字之和。第一个 for 循环计算 nums 数组中的所有数字之和。
接下来的两层 for 循环是 01 背包算法,遍历数组判断容量为 sum/2 的背包是否能够正好装满。
通过后的截图如下所示。
🔶🔶🔶🔶🔶 我是华丽的分割线 🔶🔶🔶🔶🔶
🍓五、复杂度分析
🥝5.1 时间复杂度
时间复杂度为:O(n*m),其中,n 为 nums 数组长度,m 为 nums 数组值总和的一半。在上述代码中,时间复杂度主要在「01 背包」(两层 for 循环)处,所以总的时间复杂度为 O(n * m)。
🥝5.2 空间复杂度
空间复杂度:O(m),在上述算法中,使用到了一个 dp 数组记录背包的容量,所以空间复杂度为 O(m)。
🔶🔶🔶🔶🔶 我是华丽的分割线 🔶🔶🔶🔶🔶
🍓六、总结
本题需要在理解题意的基础上,转化为 01 背包算法解决。
🎈 感觉有帮助记得「一键三连」支持下哦!有问题可在评论区留言💬,感谢大家的一路支持!🤞猿哥将持续输出「优质文章」回馈大家!🤞🌹🌹🌹🌹🌹🌹🤞
🎈 作者:
🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
🎈 关注专栏:
优质好文持续更新中……🚀🚀🚀🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
- 点赞
- 收藏
- 关注作者
评论(0)