数据结构与算法 / 系统课时

把子集划分转成背包问题

把子集划分转成背包问题

很多“把数组分成两组”或“是否存在目标子集”的题目,表面上没有背包和容量,却可以先从等式推导出一个目标和,再把每个数组元素视为只能使用一次的物品。完成这一步后,问题就变成标准的零一背包可达性判定。

学习目标

  • 从子集划分条件推导背包的目标容量
  • 根据问题目标选择布尔可达状态或最大可达值状态
  • 正确使用倒序容量更新,避免一个元素被重复选择

从划分等式得到目标容量

以“能否把正整数数组划分成两个元素和相等的子集”为例。设数组总和为 S,两个子集的和分别为 A 与 B,要求满足 A = B,同时又有 A + B = S,因此目标直接化为 A = S / 2。

这立刻给出第一个判定条件:如果 S 是奇数,S / 2 不是整数,不可能完成等和划分,可以立即返回失败。若 S 为偶数,接下来只需判断:是否能从数组中选择若干元素,使它们的和恰好等于 S / 2。

每个数组元素只能进入某个子集一次,所以它等价于一件只能选择一次、重量等于自身数值的零一背包物品。此时“容量”并不是现实中的重量,而是我们希望凑出的目标和。

类似推导也常出现在给元素添加正负号的目标和问题中。若正号元素之和为 P,负号元素之和为 N,数组总和为 S,目标为 T,则有 P - N = T 与 P + N = S,从而得到 P = (S + T) / 2。只要右侧合法,仍可转化为选择一个目标和为 P 的子集。

选择合适的状态含义

如果只关心“能不能恰好凑出目标”,最直接的是布尔状态:dp[c] 表示使用已经处理过的元素,是否能够组成和 c。初始时只有空集能组成 0,因此 dp[0] = True。

处理一个值为 x 的元素时,如果此前能组成 c - x,选择当前元素后就能组成 c,所以转移为 dp[c] = dp[c] or dp[c - x]。

另一种写法是令 dp[c] 表示容量不超过 c 时能够装入的最大元素和,然后检查最终是否有 dp[target] == target。两种状态都能解决等和划分,但布尔状态直接表达“可达性”,通常更容易阅读,也不需要保存额外的最大值信息。

状态设计 dp[c] 的含义 最终判定
布尔状态 和 c 是否可达 dp[target]
最大可达值 容量 c 内能取得的最大和 dp[target] == target

用一维零一背包完成判定

下面实现等和子集划分。容量从 target 倒序到当前元素 x,确保本轮读取的 dp[c - x] 仍然来自加入 x 之前的状态,因此每个元素最多使用一次。

python
def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True  # 空集可以组成和 0

    for x in nums:
        # 倒序更新,避免当前元素在同一轮被重复选择
        for c in range(target, x - 1, -1):
            dp[c] = dp[c] or dp[c - x]

        if dp[target]:
            return True

    return dp[target]


print(can_partition([1, 5, 11, 5]))
print(can_partition([1, 2, 3, 5]))

预期输出

text
True
False

第一组数组总和为 22,目标容量为 11,单独选择元素 11 就能达到目标,因此可以划分。第二组数组总和为 11,是奇数,在进入动态规划之前即可判定无法等分。

为什么容量必须倒序

一维数组压缩掉了“处理到第几个元素”这一维,因此更新顺序承担了隔离新旧状态的职责。倒序扫描时,计算较大的 c 所依赖的 dp[c - x] 尚未被当前元素更新,所以当前元素只会被使用一次。

若改成从小到大扫描,较小容量刚刚写出的 True 可能立刻被较大容量再次读取,相当于同一个元素可以反复选择,模型就从零一背包悄悄变成了完全背包。这不是性能差异,而是状态语义已经改变。

识别转化成立的边界

等和划分的时间复杂度为 O(n×target)O(n \times target),其中 target = S / 2,空间复杂度为 O(target)O(target)。当数组元素和很大时,即使元素个数不多,状态数组也可能很大,因此这类方法属于依赖数值大小的伪多项式算法。

这套容量模型最自然地适用于非负整数。若输入包含负数,普通的 0...target 下标无法直接覆盖负和,需要使用偏移量、集合状态或其他建模方式。对于目标和变形,还应先检查 S + T 是否为非负偶数;不满足时,推导出的目标子集和不是合法整数,可以直接判定无解。

把子集题转成背包时,最关键的不是先写循环,而是先完成等式推导:明确“要凑出的目标是多少”“每个元素能用几次”“最终只问可达还是要求最优值”。这三个问题确定后,状态类型与更新方向通常也就随之确定。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

把子集划分转成背包问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通