力扣leetcode 416.分割等和子集 动态规划 0-1背包

题目：

给你一个 只包含正整数 的 非空 数组 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

思路：

• 该题可简化为0-1背包问题。
• 关于动态规划的步骤，可以去看b站：代码随想录的视频
• 本题我参照代码随想录的五部曲步骤，练习0-1背包代码。
• 首先需要得出数组所有元素的和。
• 背包容量即为元素和的一半。
• 物品即为元素，物品的重量和价值均为它的值。

C代码：

/*
动态规划明确步骤(0-1背包问题)：
1.dp数组定义以及下标的含义：dp[j]为背包容量为j时，能放入的元素的最大值
2.得出递归公式：max(dp[j], dp[j - nums[i] + nums[i])
3.dp数组初始化为何值：0
4.明确遍历顺序：先遍历物品，再后序遍历背包
5.debug方法：打印dp数组查看
*/
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

bool canPartition(int* nums, int numsSize) {
    int sum = 0;
    for(int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    if(sum % 2) return false; // 和为奇数则不可能分割成两个元素和相等的子集
    int target = sum / 2;
    int dp[target + 1];
    memset(dp, 0, (target + 1) * sizeof(int));
    for(int i = 0; i < numsSize; i++) {
        for(int j = target; j >= nums[i]; j--) {
            dp[j] = MAX(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    return dp[target] == target;
}

原文地址：https://blog.csdn.net/chamao_/article/details/145118465

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！