led灯散热片技术支持 东莞网站建设,微信小程序ui模板,穿搭速递html网页制作代码,上海城隍庙属于哪个区题目描述#xff1a; 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。 题目链接#xff1a;LeetCode-416-分割等和子集 解题思路#xff1a;可以看成是背包问题#xff0c; 可以看成有nums.le… 题目描述 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 题目链接LeetCode-416-分割等和子集 解题思路可以看成是背包问题 可以看成有nums.length个物品是否能装满容量是 sum/2 的背包能装满说明可以返回true否则返回false。 代码实现 class Solution {public boolean canPartition(int[] nums) {// 1. dp[i]容量为 i的背包所背的最大价值为dp[i]// nums[i] 中的值既是重量也是价值// 2.递推公式dp[i]Math.max(dp[i-1][j-weight[i]]value[i],dp[i])// 放物品 i :dp[i]dp[i]// 不放物品 i :dp[i]dp[i-1][j-weight[i]]value[i]// 3. 初始化: dp[0]0// 4. 遍历顺序先物品再背包背包倒叙遍历因为每个物品只能使用一次int sum 0;for (int i 0; i nums.length; i) {sum nums[i];}if (sum % 2 1) return false;int target sum / 2;int[] dp new int[target1];for (int i 1; i nums.length; i) {for (int j target; j nums[i-1]; j--) {dp[j] Math.max(dp[j], dp[j - nums[i-1]] nums[i-1]);}if (dp[target]target){return true;}}return dp[target]target;}
}
