416. 分割等和子集

以你之姓@ 2023-10-11 18:18 115阅读 0赞

打卡!!!每日一题

今天带着大家做一道相对比较难的题目，当然我会通过讲解01背包问题带着大家过渡一下。

题目描述：

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

题目示例：  
![在这里插入图片描述][122deb8f6d9740c1aa63f4072f76e02c.png_pic_center]

再看这道题之前，我们先研究一下01背包的问题，为啥要研究01背包呢，这道题其实限制条件很明显，首先数组里的元素总和一定是偶数，其次，我们只需要能找到元素之和==sum/2的集合就可以了。

传统的「0-1背包问题」要求选取的物品的重量之和不能超过背包的总容量，这道题则要求选取的数字的和恰好等于整个数组的元素和的一半。类似于传统的「0-10−1 背包问题」，可以使用动态规划求解。

## 1.NP（0 1背包问题） ##

背包问题大致有以下几种类型：

*  01背包(有n中物品，每种物品只有一件)
 *  完全背包(有n中物品，每种物品有无限多件)
 *  多重背包(有n中物品，每种物品的个数各不相同)
 *  分组背包
 *  混合背包等

如果不是竞赛级别的背包问题，掌握01背包和完全背包就够了，其中重中之重就是01背包问题，下面我来详细讲解一下。

01背包是属于动态规划下的子类背包问题，01背包也是所有背包问题中较为简单的一类背包问题。

在leeteCode上面呢不会直接去考察01背包，而是通过一些应用类型的题目将其和01背包关联在一起，比如本题得到解法其实就是一道很纯粹的01背包问题，如果你掌握了01背包问题，这道题应该不在话下。

01背包也是最基础的背包问题，大致描述如下：

> 有n中物品，每种物品只有一件，同时每个物品呢也有自己的重量和价值，然后有一个最多只能放重量为m的背包，问这个背包能装的最多价值是多少。

特点是：每种物品只有一件，可以选择放或者不放。

我们先考虑一下暴力解法怎么去处理哈。因为每一种物品只有两种状态：

*  取
 *  不取

其实就是排列组合问题，比如我们的物品是ABC，那么对应的组合就是A、B、C、AB、AC、BC、ABC，然后计算每一个组合的价值，取最大值即可，通过递归剪枝就很容易实现。

可是我们再来看看时间复杂度是多少：2^n，这种指数爆炸式的增长，在我们的代码中一般是不会被允许的。

我举个例子带着大家一点一点的去剖析一下。

假设我们有三个物品，分别是物品1（重量：1，价值：15），物品2（重量：3，价值：20），物品3（重量：4，价值：30），背包最大容量：4，则如下所示：

我们用dp\[i\]\[j\]来表示**从0到i中任选物品，放入容量为j的背包中，获取的最大价值。**

不管01背包还是其相关子问题，都是动态规划类型的问题，动态规划的本质就是找子问题，确定状态和状态变量，确定决策并写出状态转移方程，找边界值。

ps：顺便给大家说一下动态规划下的几个步骤，建议大家背一下，笔试常考哦;

> （1）分析最优解的性质，并刻画其结构特征。  
> （2）递归的定义最优解。  
> （3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值  
> （4）根据计算最优值时得到的信息，构造问题的最优解

对于物品i，我们有两种情况：

*  放物品i
 *  不放物品i

不放物品i的话，那么dp\[i\]\[j\]对应的物品价值就是和dp\[i-1\]\[j\]的价值相同，则 d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j \] dp\[i\]\[j\]=dp\[i-1\]\[j\] dp\[i\]\[j\]=dp\[i−1\]\[j\]

放物品i的话，则 d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j − w e i g h t \[ i \] \] + v a l u e \[ i \] dp\[i\]\[j\]=dp\[i-1\]\[j-weight\[i\]\]+value\[i\] dp\[i\]\[j\]=dp\[i−1\]\[j−weight\[i\]\]\+value\[i\]

我们的最终结果就是：  
 d p \[ i \] \[ j \] = m a x ( d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j \] ， d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j − w e i g h t \[ i \] \] + v a l u e \[ i \] ) dp\[i\]\[j\]=max(dp\[i\]\[j\]=dp\[i-1\]\[j\]，dp\[i\]\[j\]=dp\[i-1\]\[j-weight\[i\]\]+value\[i\]) dp\[i\]\[j\]=max(dp\[i\]\[j\]=dp\[i−1\]\[j\]，dp\[i\]\[j\]=dp\[i−1\]\[j−weight\[i\]\]\+value\[i\]);

通过我们的状态转移方程可以看出dp\[i\]\[j\]的状态和i-1以及j的状态有关，所以在我们初始化的时候i=0以及j=0的状态都要初始化。  
j=0，我们很好理解，就是背包容量为0，那么所对应的价值也为0，。  
i=0：表示第一个物品对应的价值：

不知道大家能不能看懂我第一行和第一列为什么要这样写。

我简单解释一下：j=0时，也就是第一列，肯定对应所有的价值都是0，我们这个时候要牢记i代表的是物品，j代表的是此时背包的容量，i,j组合一起才能继续讨论背包最大的价值。

j为1，则说明最大容量是1，刚好可以放下物品0，因为物品0的重量刚好是1，同理j=2,=3均可以放入。

代码如下；

/**
         * @param n         物品数量
         * @param weights   每个物品的重量
         * @param values    每个物品的价值
         * @param maxWeight 背包最大重量
         * @return
         */
        public static int fun(int n, int[] weights, int[] values, int maxWeight) {
        
            //1.声明dp数组
            int[][] dp = new int[n][maxWeight + 1];
            //2.初始化dp数组
            for (int j = 0; j <= maxWeight; j++) {
        
                if (j >= weights[0]) {
        
                    dp[0][j] = values[0];
                } else {
        
                    dp[0][j] = 0;
                }
            }
            //3.通过状态转移方程确定每一项的最大价值
            for (int i = 1; i < n; i++) {
        
                for (int j = 1; j <= maxWeight; j++) {
        
                    //不取i
                    int value1 = dp[i - 1][j];
                    //取i 在取i之前，需要判断能否装的进i
                    int value2 = 0;
                    if (j >= weights[i]) {
        //说明装的下
                        value2 = dp[i - 1][j - weights[i]] + values[i];
                    }
                    dp[i][j] = Math.max(value1, value2);
                }
            }
            return dp[n - 1][maxWeight];
        }

不知道各位小伙伴读到这儿还有没有什么疑惑，如果没有的话，再继续向下看，如果还有疑惑，请评论区留言，我看到之后会进行解答。

下面我们回到题目：

可能看到这里，题目也忘得差不多了，我用白话给大家把题目在描述一遍：

> 问一个数组能不能等分成两个数组，等分是按照元素总和（元素和即为sum,下面要用）等分。

我在上面也说过这道题其实就是看我们从数组里面不停的去挑元素，每一个元素都有取和不取两种情况，放入最大容量为sum/2的背包里。

其实本质就是01背包的问题，不管是你笔试还是面试，不会直接去考察01背包的问题，一定是通过具体的 应用场景去考察。

我下面通过一个例子去讲解一下：  
nums=\[1,5,11,15\]  
sum=1+5+11+15=32  
sum/2=11

也就是说我们要从1，5,11,15里面挑出和为11的元素。  
dp\[i\]\[j\] 表示从数组的 \[0,i\] 下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于j

那么如何确定 dp\[i\]\[j\] 的值？需要分别考虑以下两种情况。

*  如果 j > = n u m s \[ i \] j>=nums\[i\] j>=nums\[i\]，则对于当前数字 n u m s \[ i \] nums\[i\] nums\[i\]，可以选取也可以不选取，两种情况只要有一种为true，那么 d p \[ i \] \[ j \] = t r u e dp\[i\]\[j\]=true dp\[i\]\[j\]=true
    
     *  如果不选取 n u m s \[ i \] nums\[i\] nums\[i\]，则 d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j \] dp\[i\]\[j\]=dp\[i-1\]\[j\] dp\[i\]\[j\]=dp\[i−1\]\[j\]
     *  如果选取 n u m s \[ i \] nums\[i\] nums\[i\]，则 d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j − n u m s \[ i \] \] dp\[i\]\[j\]=dp\[i-1\]\[j-nums\[i\]\] dp\[i\]\[j\]=dp\[i−1\]\[j−nums\[i\]\]
 *  如果 j < n u m s \[ i \] j<nums\[i\] j<nums\[i\]，那么就一定无法选取i,则 d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j \] dp\[i\]\[j\]= dp\[i-1\]\[j\] dp\[i\]\[j\]=dp\[i−1\]\[j\]

状态转移方程如下：  
![在这里插入图片描述][460cfcf82ee24302a18f0795f0a03132.png_pic_center]

当j=target（sum/2）的时候，dp\[i\]\[j\]就是我们最终的结果

我们再看看初始状态怎么设置：

*   j = 0 j=0 j=0的时候，我们什么都选不了，所以什么都不选即可满足，所以任意的 d p \[ i \] \[ 0 \] = t r u e dp\[i\]\[0\]=true dp\[i\]\[0\]=true。
 *  i=0的时候，只有一个 n u m s \[ 0 \] nums\[0\] nums\[0\]可选，所以 d p \[ 0 \] \[ n u m s \[ 0 \] \] = t r u e dp\[0\]\[nums\[0\]\]=true dp\[0\]\[nums\[0\]\]=true

其他状态全为 false

public class 分割等和子集_416 {
        
        public boolean canPartition(int[] nums) {
        
            int length = nums.length;
            if (length <= 1) return false;
            int sum = 0;
            int maxNum = 0;
            for (int i : nums) {
        
                sum += i;
                maxNum = Math.max(i, maxNum);
            }
            if (sum % 2 != 0) return false;
            int target = sum / 2;
            //除了maxNum 以外的所有元素之和一定小于target，
            // 因此不可能将数组分割成元素和相等的两个子集，直接返回false
            if (maxNum > target) {
        
                return false;
            }
            //1.声明dp数组
            boolean[][] dp = new boolean[length][target + 1];
            //2.初始化dp数组
            for (int i = 0; i < length; i++) {
        
                dp[i][0] = true;
            }
            dp[0][nums[0]] = true;
            //3.通过状态转移方程确定每一项的最大价值
            for (int i = 1; i < length; i++) {
        
                for (int j = 1; j <= target; j++) {
        
                    //不取i
                    boolean value1 = dp[i - 1][j];
                    //取i 在取i之前，需要判断能否装的进i
                    boolean value2;
                    if (j >= nums[i]) {
        //说明装的下
                        value2 = dp[i - 1][j - nums[i]];
                    } else {
        //装不下
                        value2 = dp[i - 1][j];
                    }
                    boolean value = value1 | value2;
                    dp[i][j] = value;
                }
            }
            return dp[length - 1][target];
        }
    
        public static void main(String[] args) {
        
            分割等和子集_416 test = new 分割等和子集_416();
            System.out.println(test.canPartition(new int[]{
        1, 5, 11, 5}));
        }
    }

[122deb8f6d9740c1aa63f4072f76e02c.png_pic_center]: https://img-blog.csdnimg.cn/122deb8f6d9740c1aa63f4072f76e02c.png#pic_center
[460cfcf82ee24302a18f0795f0a03132.png_pic_center]: https://img-blog.csdnimg.cn/460cfcf82ee24302a18f0795f0a03132.png#pic_center