网站建设仟金手指六六14,手机主页推荐,抓取网站访问量,wordpress 响应式主题目录题目分析回溯法动态规划动态规划(压缩)题目来源 416. 分割等和子集
题目分析
这道题目是要找是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。 那么只要找到集合里能够出现 sum / 2 的子集总和#xff0c;就算是可以分割成两个相同元素和子集了…
目录题目分析回溯法动态规划动态规划(压缩)题目来源 416. 分割等和子集
题目分析
这道题目是要找是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 那么只要找到集合里能够出现 sum / 2 的子集总和就算是可以分割成两个相同元素和子集了。
回溯法
这道题和39. 组合总和非常类似(可以去做一下) LeetCode-39. 组合总和
class Solution {boolean res;public boolean canPartition(int[] nums) {int sum 0;for(int i 0;inums.length;i){sum nums[i];}//如果为奇数肯定就没有两个相等的子集了if(sum % 2 1){return false;}//查找目标target的子集和int target sum / 2;backTracking(nums,0,0,target);return res;}//startIndex为了数组不选取重复元素sum为加起来的总和target目标数private void backTracking(int[] nums,int startIndex,int sum,int target){//如果sumtarget就没必要进行计算了if(sum target){return;}//如果等于直接将res设置为为true相当于是相同子集了if(sum target){res true;return;}for(int i startIndex;inums.length;i){sumnums[i];backTracking(nums,i1,sum,target);sum-nums[i]; //回溯}}
}这道题使用回溯算法不行(超时)那么就要用动态规划了
动态规划
背包问题大家都知道有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 背包问题有多种背包方式常见的有01背包、完全背包、多重背包、分组背包和混合背包等等。 要注意题目描述中商品是不是可以重复放入。 即一个商品如果可以重复多次放入是完全背包而只能放入一次是01背包写法还是不一样的。 要明确本题中我们要使用的是01背包因为元素我们只能用一次。 回归主题首先本题要求集合里能否出现总和为 sum / 2 的子集。 那么来一一对应一下本题看看背包问题如何来解决。 只有确定了如下四点才能把01背包问题套到本题上来。
背包的体积为sum / 2背包要放入的商品集合里的元素重量为 元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。
理解了0-1背包问题直接搬照着公式就可以写出 https://donglin.blog.csdn.net/article/details/129412502
class Solution {public boolean canPartition(int[] nums) {if(nums null){return false;}int sum 0;for(int num : nums){sum num;}if(sum % 2 1){return false;}int target sum / 2;int[][] dp new int[nums.length][target1];for(int jtarget;jnums[0];j--){dp[0][j] nums[0];}for(int i 1;inums.length;i){for(int j 1;jtarget;j){if(jnums[i]){dp[i][j] dp[i-1][j];}else{dp[i][j] Math.max(dp[i-1][j],dp[i-1][j-nums[i]]nums[i]);}}}return dp[nums.length-1][target]target;}
}动态规划(压缩)
动规五部曲分析如下
1.确定dp数组以及下标的含义
01背包中dp[j] 表示 容量为j的背包所背的物品价值最大可以为dp[j]。 本题中每一个元素的数值既是重量也是价值。 套到本题dp[j]表示 背包总容量所能装的总重量是j放进物品后背的最大重量为dp[j]。 那么如果背包容量为target dp[target]就是装满 背包之后的重量所以 当 dp[target] target 的时候背包就装满了。
2.确定递推公式
如果不清楚0-1背包问题的一维数组可以看这篇 https://donglin.blog.csdn.net/article/details/129437136 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。
4.确定遍历顺序
如果使用一维dp数组物品遍历的for循环放在外层遍历背包的for循环放在内层且内层for循环倒序遍历 for(int i 0;inums.length;i){for(int j target;jnums[i];j--){dp[j] Math.max(dp[j],dp[j-nums[i]]nums[i]);}}5.举例推导dp数组 完整代码
class Solution {public boolean canPartition(int[] nums) {if(nums null){return false;}int sum 0;for(int num : nums){sum num;}if(sum % 2 1){return false;}int target sum / 2;int[] dp new int[target1];for(int i 0;inums.length;i){for(int j target;jnums[i];j--){//物品 i 的重量是 nums[i]其价值也是 nums[i]dp[j] Math.max(dp[j],dp[j-nums[i]]nums[i]);}}return dp[target] target;}
}
