子集和问题[编辑 | 编辑源代码]

子集和问题（Subset Sum Problem）是计算机科学中一个经典的NP完全问题，属于组合优化领域。该问题描述为：给定一个包含n个正整数的集合S和一个目标整数T，判断是否存在S的一个子集，使得该子集中的元素之和等于T。这个问题在密码学、资源分配、决策优化等领域有广泛应用。

问题定义[编辑 | 编辑源代码]

给定：

一个正整数集合 $S = {s_{1}, s_{2}, \dots, s_{n}}$
一个目标值 $T$

问是否存在一个子集 $S^{'} \subseteq S$ ，使得 $\sum_{s \in S^{'}} s = T$ 。

解决方法[编辑 | 编辑源代码]

回溯法[编辑 | 编辑源代码]

回溯法是一种通过递归尝试所有可能的子集来解决问题的算法。其核心思想是逐步构建候选解，并在发现当前路径无法满足条件时回溯。

算法步骤[编辑 | 编辑源代码]

1. 从第一个元素开始，尝试将其包含在子集中。 2. 递归检查剩余元素是否能满足剩余的目标和。 3. 如果包含当前元素导致和超过目标值，则回溯并尝试不包含该元素的情况。 4. 重复上述过程直到遍历所有可能。

代码示例[编辑 | 编辑源代码]

def subset_sum_backtrack(S, T):
    def backtrack(start, target, path):
        if target == 0:
            return path
        for i in range(start, len(S)):
            if S[i] > target:
                continue
            res = backtrack(i + 1, target - S[i], path + [S[i]])
            if res is not None:
                return res
        return None
    return backtrack(0, T, [])

# 示例输入
S = [3, 34, 4, 12, 5, 2]
T = 9
# 输出
print(subset_sum_backtrack(S, T))  # 输出: [4, 5]

分支限界法[编辑 | 编辑源代码]

分支限界法通过剪枝策略减少搜索空间，通常比回溯法更高效。它使用优先队列（或堆）来选择最有希望的节点进行扩展。

算法步骤[编辑 | 编辑源代码]

1. 将初始状态（空子集，目标和为T）加入优先队列。 2. 每次从队列中取出一个状态，生成两个子状态：

  * 包含当前元素，更新剩余目标和。
  * 不包含当前元素，保持目标和不变。

3. 如果剩余目标和为0，返回解；否则继续扩展。

代码示例[编辑 | 编辑源代码]

import heapq

def subset_sum_branch_bound(S, T):
    heap = []
    heapq.heappush(heap, (0, 0, []))  # (priority, index, path)
    while heap:
        _, idx, path = heapq.heappop(heap)
        if sum(path) == T:
            return path
        if idx >= len(S):
            continue
        # 包含当前元素
        new_path = path + [S[idx]]
        if sum(new_path) <= T:
            heapq.heappush(heap, (sum(new_path), idx + 1, new_path))
        # 不包含当前元素
        heapq.heappush(heap, (sum(path), idx + 1, path))
    return None

# 示例输入
S = [3, 34, 4, 12, 5, 2]
T = 9
# 输出
print(subset_sum_branch_bound(S, T))  # 输出: [4, 5]