从理论到实践：01背包问题在分割等和子集中的应用（力扣416）

文章目录

• 题目
• 题解
• • 一、思路
  • 二、解题方法
  • 三、Code
• 总结

在昨天的文章（传送门）中，我们从理论对01背包问题进行了基础详细的讲解，从二维数组到一维数组进行优化，今天我们用实际题目来运用一下01背包问题的动态规划，要使用01背包问题中的一维dp数组解题，如果对这个不清楚的话，可以先观看上期视频了解01背包一维dp数组的使用方法，相信结合上期文章再观看本文会理解的更加透彻

题目

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

题解

一、思路

看到这个题目要求，要求集合中出现两个和为sum/2的子集，可以看作将nums数组里面的元素放进子集中能出现满足sum/2的情况，nums数组每个元素只能用一次，集合里的元素可以看作01背包中的物品，每个物品只能用一次，而背包体积自然就是sum/2，元素(物品)的重量和价值是相等的都为元素的数值nums[i]

可以将本题与上期01背包结合，转化得到下表：

二、解题方法

动规五部曲

1. 确定dp数组及下标i的含义：dp[j]表示 子集总容量（所能装的总重量）是j，放进元素后，子集中的最大重量为dp[j]。如示例1中：target为11，dp[11]表示子集的和为11，放进nums数组中的元素[1,5,5]或[11]后，子集的最大重量为dp[11]，那么如果背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。

2. 确定递推公式：由01背包问题的一维dp数组递推公式与nums数组里的元素的重量和价值相等得出dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

// 标准01背包问题的一维dp数组：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

//分割等和子集的一维dp数组
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

3. dp数组如何初始化：dp[0]表示子集和为0，所以dp[0]=0，其它非零下标的dp数组就可以像01背包问题一样取0即可，保证会被递推过程中的最大值覆盖掉

int[] dp = new int[target+1];

4. 确定遍历顺序：同样是先从前到后遍历物品，再倒序遍历背包容量，只是在这里，物品是nums数组里的每个元素nums[i]，最大的背包容量则是子集要求的sum/2，当内层的for循环背包总容量小于元素的值的话，说明背包已经装不下元素了，此时就看子集是否刚好装满元素，如果已经满足等和子集了，那么提前就返回true

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;
    }
}

5. 举例推导dp数组：dp[j]的数值一定是小于等于j的，例如在示例一中dp[8]=7，无论怎么样放元素都不会有子集和为8的情况出现，如果dp[j] == j 说明，集合中的元素总和正好可以凑成子集总和j，最后dp[11] = 11说明可以将这个数组分割成两个子集，使得两个子集的元素和相等

三、Code

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }

        // 剪枝：和若为奇数无法进行分割等和
        if(sum % 2 != 0) {
            return false;
        }
        // 背包的体积为和的一半
        int target = sum / 2;
        int[] dp = new int[target+1];
        // 先遍历物品，再倒序遍历背包容量
        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;
    }
}

总结

通过这篇博客，读者可以清晰地了解如何结合01背包问题在实际问题中的使用，本题的关键在于想到是否可以从输入数组中挑选出一些正整数，使得这些数的和 等于 整个数组元素的和的一半，再抽象成一个01背包问题。
希望本文能够帮助读者更好地理解和应用动态规划算法在01背包问题中的使用，如果有任何疑问或者建议，欢迎留言讨论