当前位置: 首页> 汽车> 新车 > 【代码随想录】【算法训练营】【第41天】 [416]分割等和子集

【代码随想录】【算法训练营】【第41天】 [416]分割等和子集

时间:2025/7/11 22:47:11来源:https://blog.csdn.net/weixin_54954007/article/details/139746176 浏览次数: 0次

前言

思路及算法思维,指路 代码随想录。
题目来自 LeetCode。

day 40,休息,休息一下~
day 41,艰难的周一~

题目详情

[416] 分割等和子集

题目描述

416 分割等和子集
416 分割等和子集

解题思路

前提:是否可以将数组分为和相等的两个子集,每个元素只能使用一次
思路:动态规划,0-1背包问题
重点:0-1背包问题的二维数组dp[i][j]的含义与实现;一维数组dp[j]的实现,尤其是遍历顺序的区别。

代码实现

C语言
二维数组dp[i][j]
// 0-1背包问题, 二维数组dp[i][j]: 从下标[0, i]中选取元素,限制在大小为j中的最大元素和
// dp[i][j] = max((dp[i-1][j-nums[i]] + nums[i]), dp[i-1][j])
int sumFun(int *nums, int numsSize)
{int sumTmp = 0;for (int i = 0; i < numsSize; i++) {sumTmp += nums[i];}return sumTmp;
}int maxFun(int p1, int p2)
{return p1 > p2 ? p1 : p2;
}bool canPartition(int* nums, int numsSize) {int sum = sumFun(nums, numsSize);if (sum % 2 == 1) {return false;}int target = sum / 2;int dp[numsSize][target + 1];// 初始化dp数组for (int j = 0; j <= target; j++) {if (j < nums[0]) {dp[0][j] = 0;} else {dp[0][j] = nums[0];}}// 从前向后遍历for (int i = 1; i < numsSize; i++) {for (int j = 0; j <= target; j++) {if (j < nums[i]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = maxFun((dp[i - 1][j - nums[i]] + nums[i]), dp[i - 1][j]);}}}if (dp[numsSize - 1][target] == target) {return true;}return false;
}
一维数组dp[j]

由于每个元素只能使用一次,所以对于内层遍历的元素和,需要从大到小遍历,即dp[j]的赋值不会引起dp[j-1]的数值变化,即从小到大遍历,会使元素i使用多次。

// 0-1背包问题, 一维数组dp[j]: 从下标[0, i]中选取元素,限制在大小为j中的最大元素和
// dp[j] = max((dp[j-nums[i]] + nums[i]), dp[j])
int sumFun(int *nums, int numsSize)
{int sumTmp = 0;for (int i = 0; i < numsSize; i++) {sumTmp += nums[i];}return sumTmp;
}int maxFun(int p1, int p2)
{return p1 > p2 ? p1 : p2;
}bool canPartition(int* nums, int numsSize) {int sum = sumFun(nums, numsSize);if (sum % 2 == 1) {return false;}int target = sum / 2;int dp[target + 1];// 初始化dp数组for (int i = 0; i < target + 1; i++) {dp[i] = 0;}// 从前向后遍历元素,从后向前遍历元素和for (int i = 0; i < numsSize; i++) {for (int j = target; j >= nums[i]; j--) {dp[j] = maxFun((dp[j - nums[i]] + nums[i]), dp[j]);}}if (dp[target] == target) {return true;}return false;
}

今日收获

  1. 0-1背包问题:dp数组的含义、初始化、递推公式;dp数组的二维实现、一维实现;物品、背包容积的先后遍历顺序、以及每个维度的大小遍历顺序。
关键字:【代码随想录】【算法训练营】【第41天】 [416]分割等和子集

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: