[416][中等][动态规划][背包] 分割等和子集

题目描述

416. 分割等和子集

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

注意:

• 每个数组中的元素不会超过 100

• 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

解题思路

如果数组中的数字之和是奇数, 肯定找不到两个子集的元素和相等. 偶数才能划分成两个和相等的子集.

现在问题就转化成了能否找到一个子序列的和为sum(raw_list) // 2. 这种在原列表中找出一个子集, 使得子集的和为一个指定数字的问题, 一般转换为背包问题来解决.

以背包问题的思路考虑, 物品是数组中的每一个数, 背包容量就是原数组之和的一般. 由于数组中每个元素只能用1次, 因此这是一个01背包的问题.

每个元素对应的重量就是自身的数值大小, 价值也可以为自身的数值大小. 问题就变成状态矩阵dp[-1][-1]的值是否等于原数组之和的一般. 如果等于说明可以找到一组元素组成子序列, 其和等于原数组之和的一半.

使用滚动数组的代码如下:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        total = sum(nums)
        if total % 2 == 1:
            return False
        target = total // 2
        cache = [0] * (target + 1)

        for i in range(n):
            for j in range(target, nums[i] - 1, -1):
                cache[j] = max(cache[j], cache[j - nums[i]] + nums[i])
        return cache[-1] == target

恰好装满

上面还是在按照背包问题的传统思路在走. 背包问题的一种扩展就是能否恰好装满指定容量背包的问题. 这个情况在背包问题中有说明.

本题中, 我们不关心装满背包后的价值, 只关心能否恰好装满. 因此状态矩阵的定义可以修改为: dp[i][j]代表使用前i个物品, 能否恰好装满容量为j的背包. 因此dp中的值为True/False. 对应的状态转移公式也变为:

dp[i][j] = dp[i - 1][j] or dp[i - 1][j - w[i]]

即考虑当前物品i装与不装入背包两种情况, 只要有一种情况符合就可以.

初始化全部为False, 除了dp[i][0]要 初始化为True. 因此恰好装入容量为0的背包, 只需要什么都不装就可以了.

使用滚动数组的代码如下:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        total = sum(nums)
        if total % 2 == 1:
            return False
        target = total // 2
        cache = [False] * (target + 1)
        cache[0] = True

        for i in range(n):
            for j in range(target, nums[i] - 1, -1):
                cache[j] = cache[j] or cache[j - nums[i]]
        return cache[-1]