网站开发的历史,wordpress主题手动安装,甘肃省住房和城乡建设部网站,课程网站建设论文分割等和子集
力扣原题链接 给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。 示例 1#xff1a; 输入#xff1a;nums [1,5,11,5] 输出#xff1a;true 解释#xff1a;数组可以分割成 [1, 5, 5] …分割等和子集
力扣原题链接 给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 示例 1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。 提示 1 nums.length 200 1 nums[i] 100 01背包理论 (解决能不能装满背包的问题)
分析
分成两个子集且元素和相同可以看成将原来的所有元素加和除以2这不就分成两个子集元素和相同了嘛。然后确定一个子集里的元素和是一半另一个子集自动旧是另一半。然后我们可以将数组中的每个元素看作是一种物品每个物品的价值value等于它的数值而背包的容量capacity等于数组元素的和的一半。我们的目标是尝试将这些物品放入背包中使得背包的价值恰好等于容量的一半。注意如果元素和本来就不能分成两份那么直接返回·false·。
状态定义
我们定义一个二维的动态规划数组 dp其中 dp[i][j] 表示在前 i 个物品中能否选取一些物品使得它们的总和等于 j。
状态转移方程
在状态转移方程中我们需要考虑当前物品是否放入背包中的两种情况
如果不放入当前物品 nums[i - 1]则 dp[i][j] dp[i - 1][j]如果放入当前物品 nums[i - 1]则 dp[i][j] dp[i - 1][j - nums[i - 1]]。
综合以上两种情况状态转移方程为
dp[i][j] dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]初始化
我们需要对动态规划数组进行初始化当没有物品或背包容量为0时。
Java解题
class Solution {public boolean canPartition(int[] nums) {int sum 0;for(int a : nums){sum a;}if(sum % 2 !0){return false;}int t sum/2;int dp [] new int[t1];for(int i 0 ;i nums.length ;i ){//遍历物品for (int j t ; j nums[i] ;j--){//遍历背包 倒序dp[j] Math.max(dp[j],dp[j-nums[i]]nums[i]);//背包最大价值的递推公式}}if(dp[t] t ){//判断背包是否装满return true;}else{return false;}}
}解题思路总结
通过以上步骤我们可以分析出解决该问题的关键步骤并用动态规划的思想进行解决。首先计算数组的总和然后判断是否为偶数如果不是偶数则返回false。接着根据动态规划的思想初始化dp数组然后按照状态转移方程进行状态转移最终返回dp数组的最后一个值。
