富阳区建设工程质监站网站,建站 discuz,南昌网站建设规划方案,wordpress做企业官网好不好416. 分割等和子集
我们的目标是尝试从这些数字中选取一部分数字#xff0c;使得它们的和恰好等于数组总和的一半。这相当于在背包容量为总和的一半的情况下#xff0c;尝试装入物品#xff0c;看是否能够恰好装满背包。
class Solution {public boolean canPartition(int…416. 分割等和子集
我们的目标是尝试从这些数字中选取一部分数字使得它们的和恰好等于数组总和的一半。这相当于在背包容量为总和的一半的情况下尝试装入物品看是否能够恰好装满背包。
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;}
}
1049.最后一块石头的重量II
本题其实就是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就化解成01背包问题了跟上一题一样。
class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for (int i : stones) {sum i;}int target sum 1;//初始化dp数组int[] dp new int[target 1];for (int i 0; i stones.length; i) {//采用倒序for (int j target; j stones[i]; j--) {//两种情况要么放要么不放dp[j] Math.max(dp[j], dp[j - stones[i]] stones[i]);}}return sum - 2 * dp[target];}
}
494.目标和
假设加法的总和为x那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) targetx (target sum) / 2此时问题就转化为装满容量为x的背包有几种方法。
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for (int i 0; i nums.length; i) sum nums[i];//如果target过大 sum将无法满足if ( target 0 sum -target) return 0;if ((target sum) % 2 ! 0) return 0;int size (target sum) / 2;if(size 0) size -size;int[] dp new int[size 1];dp[0] 1;for (int i 0; i nums.length; i) {for (int j size; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[size];}
}
