南昌网站排名优化报价,无锡网络营销推广公司,东营高端网站建设,山东通app官网下载二维码给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。 示例 1#xff1a; 输入#xff1a;nums [1,5,11,5]
输出#xff1a;true
解释#xff1a;数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2使得两个子集的元素和相等。 示例 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 01背包问题 背包问题大家都知道有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 01背包一维滚动数组递推公式dp[j] max(dp[j], dp[j - weight[i]] value[i]); 本题如何转换到01背包问题是关键我们想一想题目说分割两个等和子集那只需要是sum/2得到一个子集的体积这个sum/2得到的相当于就是一个背包这个背包体积是sum/2看nums里面能否把这个背包体积装满如果能装满即可以分割等和子集。对应01背包问题这题注意的点是背包要放入的商品集合里的元素重量为元素的数值价值也为元素的数值其次背包中每一个元素是不可重复放入。动规五部曲dp含义、递推公式、初始化、遍历顺序、打印数组 dp含义dp[j]表示容量为j的背包所背的物品价值最大可以为dp[j]。 递推公式本题中每一个元素的数值既是重量也是价值。所以 dp[j] max(dp[j], dp[j - nums[i]] nums[i]); 初始化背包容量为j0物品最大价值为dp[0]0这个好理解那其他下标初始化也为0是为什么呢因为dp数组在递推的过程中取得最大的价值把下标初始成负无穷小就不会被初始值覆盖这里初始为0即可也是一样的。 遍历顺序 这里是用一维滚动数组来解决所以物品遍历的for循环放在外层遍历背包的for循环放在内层然后题目说物品i只能放一次所以且内层for循环倒序遍历 因为倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了那么物品0就会被重复加入多次
打印数组当遇到疑惑或者提交错误时打印数组出来比较快速的看看哪一步有错。
以下是我在力扣c语言提交的代码仅供参考 一维滚动数组
bool canPartition(int* nums, int numsSize) {//给出容量和数值大小范围求的还是一半所以数组大小为200*100/21int dp[10001]{0};int sum 0;int target 0;for(int i 0;inumsSize;i){sum nums[i];}//如果总和为偶数说明可以分割等和子集反之if(sum % 2 0){target sum / 2;}else if(sum % 2 ! 0){return false;}//初始化memset(dp,0,sizeof(dp));dp[0] 0;//先遍历物品for(int i 0;inumsSize;i){//再遍历背包且是倒序遍历保证物品i只被放入一次for(int j target;jnums[i];j--){//01背包递推公式dp[j] max(dp[j], dp[j - weight[i]] value[i]);//本题中每一个元素的数值既是重量也是价值dp[j] dp[j] dp[j-nums[i]] nums[i] ? dp[j] : dp[j-nums[i]] nums[i];}}//如果dp[target] target//说明可以将这个数组分割成两个子集使得两个子集的元素和相等。if(dp[target] target) return true;return false;
}
在此也给出二维数组的求解
bool canPartition(int* nums, int numsSize) {int sum 0;for(int i 0;inumsSize;i){sum nums[i];}if(sum % 2 1){return false;}int traget sum / 2;int dp[numsSize1][traget1];memset(dp,0,sizeof(dp));for(int i nums[0];itraget;i){dp[0][i]nums[0];}for(int i 1;inumsSize;i){for(int j 0;jtraget;j){if(jnums[i]){dp[i][j] dp[i-1][j];}else{dp[i][j] dp[i-1][j] (dp[i-1][j-nums[i]]nums[i]) ? dp[i-1][j]: (dp[i-1][j-nums[i]]nums[i]);}}}if(dp[numsSize-1][traget] traget){return true;}else{return false;}
}
