开个网站建设公司多少钱,广东省住房和城乡建设局官网,设计师网课,福田网站建设公司416. 分割等和子集 文章目录 [416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/)一、题目二、题解方法一#xff1a;0-1背包二维数组方法二#xff1a;0-1背包一维数组 一、题目
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将…416. 分割等和子集 文章目录 [416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/)一、题目二、题解方法一0-1背包二维数组方法二0-1背包一维数组 一、题目
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 。示例 2
输入nums [1,2,3,5]
输出false
解释数组不能分割成两个元素和相等的子集。提示
1 nums.length 2001 nums[i] 100
二、题解
方法一0-1背包二维数组
步骤1理解题目以及01 背包问题
在 01 背包问题中我们有一系列物品每个物品有自己的重量和价值目标是选择一些物品放入背包中使得背包的总重量不超过一定限制同时所选物品的总价值最大。
题目要求将数组分割成两个子集使得两个子集的元素和相等。这实际上就是在数组中寻找一个子集使得这个子集的元素和等于整个数组元素和的一半。如果能找到这样的子集那么剩余的元素的和也必然等于整个数组元素和的一半。
步骤2将问题转化为 01 背包问题
将这道题目与 01 背包问题联系起来可以将数组元素看作是物品的重量而数组元素的值看作是物品的价值。我们的目标是将这些物品放入“背包”中使得背包的总重量等于数组元素和的一半同时价值最大。如果我们能找到一种放置物品的方式使得背包中的物品总价值等于数组元素和的一半那么剩余的物品总价值也必然等于数组元素和的一半从而满足题目要求。
步骤3套用0-1背包问题动态规划思路
在 01 背包问题中动态规划的状态转移方程通常是
dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])其中dp[i][j] 表示在前 i 个物品中背包的容量为 j 时的最大价值weight[i] 表示第 i 个物品的重量value[i] 表示第 i 个物品的价值。
在本题中dp[i][j]
i: 表示考虑前 i 个元素或前 i 个物品类比于 01 背包问题中的物品。j: 表示目标数值即我们希望在考虑前 i 个元素的情况下能够凑出的元素和或背包的容量类比于 01 背包问题中的背包容量。
因此dp[i][j] 的含义是在考虑前 i 个元素的情况下能否凑出元素和等于 j。
具体来说dp[i][j] 可以有两种可能的取值
如果可以在考虑前 i-1 个元素的情况下凑出元素和等于 j那么我们不需要使用第 i 个元素所以 dp[i][j] dp[i-1][j]。如果可以在考虑前 i-1 个元素的情况下凑出元素和等于 j-nums[i]那么我们可以使用第 i 个元素所以 dp[i][j] dp[i-1][j-nums[i]]。
步骤4初始化和边界条件
vectorvectorint dp(nums.size(),vectorint(sum/21,0));
for(int i 0; i sum/2 1; i){if(nums[0] i){dp[0][i] nums[0];}
}将 dp 数组的第一行中的值初始化为 0然后对于第一行中的某个位置 dp[0][i]如果 nums[0] i说明第一个元素可以放入背包中凑出和为 i所以将其值设为 nums[0]第一列因为j本身代表元素和因此j 0时nums[0][j] 0.
步骤5填充动态规划表
我们使用两个循环来遍历动态规划数组 dp 的每个位置。其中 i 表示考虑前 i 个元素j 表示目标数值。
i 循环我们从 i 1 开始遍历因为 i 0 的情况已经在初始化部分处理过了我们从第二个元素开始考虑。j 循环我们从 j 1 开始遍历因为不需要考虑元素和为 0 的情况从小到大逐步考虑不同的目标数值。
在每个位置 (i, j)我们需要根据当前的元素值 nums[i] 以及目标数值 j判断是否可以在前 i 个元素中凑出元素和为 j。我们有两种选择
如果当前元素值 nums[i] 大于目标数值 j那么无法将当前元素放入凑出目标数值因此 dp[i][j] dp[i-1][j]即继承前一个状态的值。如果当前元素值 nums[i]小于等于目标数值 j我们有两种选择 选择不将当前元素放入那么 dp[i][j] dp[i-1][j]。选择将当前元素放入我们需要在前 i-1 个元素中寻找一种组合使得元素和为 j-nums[i]并且将当前元素值 nums[i] 加上。因此dp[i][j] max(dp[i-1][j-nums[i]] nums[i], dp[i-1][j])即选择两种选择中的较大值。
通过这两种选择我们可以逐步填充 dp 数组最终得到在不同元素和的情况下是否存在一种组合方式使得元素和接近或等于目标数值。这就是动态规划状态转移的过程通过不断更新 dp 数组中的值我们可以在最后的状态中找到问题的解。
for(int i 1; i nums.size(); i){for(int j 1; j sum/21; j){if(j nums[i]){dp[i][j] dp[i-1][j];} else {dp[i][j] max(dp[i-1][j-nums[i]] nums[i], dp[i-1][j]);}}
}步骤6寻找答案
在填充完整个 dp 数组后我们需要寻找一个子集使得其元素和等于整个数组元素和的一半。我们可以在 dp[i][sum/2] 处找到这个值如果等于 sum/2则表示存在这样的子集返回 true否则返回 false。 for(int i 0; i nums.size(); i){if(dp[i][sum/2] sum/2){return true;}}return false;总代码和上面有一点点不同进行了一定的变量改进
class Solution {
public:bool canPartition(vectorint nums) {int sum 0;for(int i 0; i nums.size(); i){sum nums[i];}// 如果数组元素和为奇数无法分割成两个元素和相等的子集if(sum % 2 1){return false;}int target sum / 2; // 目标数值为元素和的一半vectorvectorint dp(nums.size(),vectorint(target1,0));// 初始化第一行表示只考虑第一个元素时的情况for(int i 0; i target 1; i){if(nums[0] i){dp[0][i] nums[0];} }// 填充动态规划数组for(int i 1; i nums.size(); i){for(int j 1; j target 1; j){if(j nums[i]){// 当前元素值大于目标数值无法放入背包dp[i][j] dp[i-1][j];}else{// 选择放入当前元素或不放入取较大值dp[i][j] max(dp[i-1][j-nums[i]]nums[i], dp[i-1][j]);}}}// 检查是否有一种组合方式使得元素和等于目标数值for(int i 0; i nums.size(); i){if(dp[i][target] target){return true;}}return false;}
};方法二0-1背包一维数组
思路和上面大差不差但是可以节约空间。
class Solution {
public:bool canPartition(vectorint nums) {int sum 0;for(int i 0; i nums.size(); i){sum nums[i];}// 如果数组元素和为奇数无法分割成两个元素和相等的子集if(sum % 2 1){return false;}int target sum / 2; // 目标数值为元素和的一半vectorint dp(target1, 0); // 使用一维数组来保存状态// 填充动态规划数组for(int i 0; i nums.size(); i){// 注意循环条件是 j nums[i]从后往前遍历for(int j target; j nums[i]; j--){// 选择放入当前元素或不放入取较大值dp[j] max(dp[j-nums[i]] nums[i], dp[j]);}}// 检查是否有一种组合方式使得元素和等于目标数值if(dp[target] target){return true;}return false;}
};
