苏华建设集团有限公司网站,wordpress 普通文本 quot,网店代运营就是个坑,池州做网站416. 分割等和子集
416. 分割等和子集 - 力扣#xff08;LeetCode#xff09;
代码随想录 (programmercarl.com)
动态规划之背包问题#xff0c;这个包能装满吗#xff1f;| LeetCode#xff1a;416.分割等和子集_哔哩哔哩_bilibili 给你一个 只包含正整数 的 非空 数组…416. 分割等和子集
416. 分割等和子集 - 力扣LeetCode
代码随想录 (programmercarl.com)
动态规划之背包问题这个包能装满吗| LeetCode416.分割等和子集_哔哩哔哩_bilibili 给你一个 只包含正整数 的 非空 数组 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 找到集合里能够出现 sum / 2 的子集总和就算是可以分割成两个相同元素和子集了。
该题中的元素只能使用一次所以是01背包问题。
背包要放入的商品集合里的元素重量为 元素的数值价值也为元素的数值。
动规五部曲
1、确定dp数组以及下标的含义dp[j]表示容量为j的背包所背物品的最大价值也为dp[j];
2、确定递推公式dp[j]max(dp[j] dp[j]-weight[i]value[i])本题中nums[i] val[i], 所以dp[j] max(dp[j]dp[j-nums[i]]num[i])
3、dp数组如何初始化dp[0] 0;非0下标的元素初始为0
4、确定遍历顺序一维dp数组的循环中物品在外背包在内
5、举例推导dp数组 综合代码
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 - 20msif(dp[target] target)return true;}return dp[target] target;}
}
