01背包

题目

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

注：注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例1

  • 输入: [1, 5, 11, 5]
  • 输出: true
  • 解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例2

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

思路

初步看这个题是要把给定数组分成两个子集，使其总和相等，那么我们只需要在集合中找出sum/2的子集总和，就可以分割成相同元素和子集了。

！那么这道题就很适合用01背包来做了，这道题中我们的元素只能取一次，首先我们可以把背包大小定为我们所需要寻找的sum/2的子集和，其给定数组的元素的重量和价值都是数组元素值，我们只需写出递推公式，然后再去查看是否有子集能填满容量sum/2。

总结一下便是以下四点：

背包的体积为sum/2
背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum/2的子集。
背包中每一个元素是不可重复放入。

动态规划五步曲

  1. 确定dp数组以及下标的含义

01背包中，dp[j]表示： 容量为j的背包，所背的物品价值最大可以为dp[j]。本题中每一个元素的数值既是重量，也是价值。

套到本题，dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。

  1. 确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

  1. dp数组如何初始化

从dp[j]的定义来看，首先dp[0]一定是0。

如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。

这样才能让dp数组在递推的过程中取得最大的价值，而不是被初始值覆盖了。

  1. 确定遍历顺序
    如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
1
2
3
4
5
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]);
    }
}
  1. 举例推导dp数组

如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

注：dp[j]的数值一定是小于等于j的。

用例1，输入[1,5,11,5] 为例，如图：
01背包
最后dp[11] == 11，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。

《代码随想录》算法公开课
力扣题目链接

代码实现-一维dp数组

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
class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int n = nums.length;
        int sum = 0;
        //求数组总和
        for(int num : nums) {
            sum += num;
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;

        int target = sum / 2;
        //本题所给数组是非零整数，则将所有值初始为0
        int[] dp = new int[target + 1];

        //先遍历物品，再去遍历背包大小
        for(int i = 0; i < n; i++) {
            for(int j = target; j >= nums[i]; j--) {
                //物品 i 的重量是 nums[i]，其价值也是 nums[i]
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
           
            //剪枝一下，每一次完成内层的for-loop，立即检查是否dp[target] == target，优化时间复杂度（26ms -> 20ms）
            if(dp[target] == target)
                return true;
        }
        return dp[target] == target;
    }
}

代码实现-二维dp数组

看不懂的话详见动态规划-01背包理论基础(一)

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
class Solution {
    public boolean canPartition(int[] nums) {
        
        int len = nums.length;
      
        if(len == 0)
            return false;
        //记录数组总和
        int sum = 0;
        for (int num : nums)
            sum += num;
        //总和为奇数直接不满足题意返回false
        if(sum % 2 == 1)
            return false;

        int target = sum / 2;

        //定义数组大小
        int[][] dp = new int[nums.length][target + 1];

        //对dp数组进行初始化
        for(int j = nums[0]; j <= target; j++){
            dp[0][j] = nums[0];
        }

        for(int i = 1; i < len; i++){
            for(int j = 0; j <= target; j++){
                if (j < nums[i]) 
                    dp[i][j] = dp[i - 1][j];
                else 
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
            }
        }

        return dp[len - 1][target] == target;
    }
}