训练营第四十二天 | 01背包问题，你该了解这些！ ● 01背包问题，你该了解这些！ 滚动数组 ● 416. 分割等和子集
01背包问题 二维
代码随想录
dp二维数组
优化
01背包问题 一维
代码随想录
dp一维数组
416. 分割等和子集
把数组分成总和相等的两份，如果数组总和为奇数，不能分割，若有符合的数组子集，返回true
代码随想录
class Solution {public boolean canPartition(int[] nums) {int sum = 0;//计算总和for(int i = 0; i < nums.length; i++) {sum += nums[i];}int target = sum >> 1;//将总和分成相等的两份if(sum % 2 == 1) return false;//总和为奇数不可能分割两个完全一样的数组int[] dp = new int[target+1];//dp[j]指容量为j时 所容纳的物品最大价值for(int i = 0; i < nums.length; i++) {//物品for(int j = target; j >= nums[i]; j--) {//背包dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);//最大价值if(dp[target] == target) return true;//判断最大价值是否等于背包容量}}return dp[target] == target;}
}