416. 分割等和子集

打卡!!!每日一题

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

题目描述：

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

题目示例：

再看这道题之前，我们先研究一下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]的价值相同，则$dp[i][j]=dp[i-1][j]$

放物品i的话，则$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];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

下面我们回到题目：

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

问一个数组能不能等分成两个数组，等分是按照元素总和（元素和即为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>=nums[i]$，则对于当前数字$nums[i]$，可以选取也可以不选取，两种情况只要有一种为true，那么$dp[i][j]=true$
  • 如果不选取$nums[i]$，则$dp[i][j]=dp[i-1][j]$
  • 如果选取$nums[i]$，则$dp[i][j]=dp[i-1][j-nums[i]]$
• 如果$j<nums[i]$，那么就一定无法选取i,则$dp[i][j]=dp[i-1][j]$

状态转移方程如下：

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

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

• $j=0$的时候，我们什么都选不了，所以什么都不选即可满足，所以任意的$dp[i][0]=true$。
• i=0的时候，只有一个$nums[0]$可选，所以$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}));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49