2024-12-09
1.3k 字
5 分钟
LeetCode-分割等和子集
题目
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注：注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
示例1
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例2
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
思路
初步看这个题是要把给定数组分成两个子集，使其总和相等，那么我们只需要在集合中找出sum/2的子集总和，就可以分割成相同元素和子集了。
！那么这道题就很适合用01背包来做了，这
2024-12-06
1.7k 字
6 分钟
动态规划-01背包理论基础(二)
动态规划-01背包理论基础(二)
上一篇我们提到了01背包的二维的dp数组，这篇我们就来说一说01背包的一维数组，也就是滚动数组，为什么叫滚动数组看完接下来的分析你就懂了！
那么我们通过01背包，来彻底讲一讲滚动数组！
接下来还是用如下这个例子来进行讲解：
weight = [1, 3, 4]
value = [15, 20, 30]
一维dp数组（滚动数组）
对于背包问题其实状态都是可以压缩的!
在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[
2024-12-05
1.6k 字
6 分钟
动态规划-01背包理论基础(一)
动态规划：01背包理论基础(一)
背包分类图
什么是01背包？
01背包
有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
关于其他背包
除01背包以外其他类型的背包，面试几乎不会问，都是竞赛级别的了，leetcode上连多重背包的题目都没有，所以题库也告诉我们，01背包和完全背包就够用了。
而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。
所以背包问题的理论基础重中之重是01背包，一定要理解透！
举个栗子
weight = [1
