编辑“︁子集和问题”︁（章节）

= 子集和问题 =

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

== 问题定义 ==
给定：
* 一个正整数集合 <math>S = \{s_1, s_2, \dots, s_n\}</math>
* 一个目标值 <math>T</math>

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

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

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

==== 代码示例 ====
<syntaxhighlight lang="python">
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]
</syntaxhighlight>

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

==== 算法步骤 ====
1. 将初始状态（空子集，目标和为''T''）加入优先队列。
2. 每次从队列中取出一个状态，生成两个子状态：
   * 包含当前元素，更新剩余目标和。
   * 不包含当前元素，保持目标和不变。
3. 如果剩余目标和为0，返回解；否则继续扩展。

==== 代码示例 ====
<syntaxhighlight lang="python">
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]
</syntaxhighlight>

== 复杂度分析 ==
* '''回溯法'''：最坏情况下时间复杂度为<math>O(2^n)</math>，因为需要检查所有子集。
* '''分支限界法'''：时间复杂度取决于剪枝效果，最坏情况下仍为<math>O(2^n)</math>，但实际运行中通常优于回溯法。

== 实际应用案例 ==
1. '''金融投资组合优化'''：选择一组投资项目的子集，使其总收益等于目标值。
2. '''库存管理'''：从库存中选择物品的子集，使其总重量或总价值等于目标值。
3. '''密码学'''：某些加密算法利用子集和问题的难解性设计公钥系统。

== 可视化示例 ==
<mermaid>
graph TD
    A[初始集合: [3, 34, 4, 12, 5, 2], T=9] --> B[包含3?]
    B -->|是| C[剩余目标:6, 路径:[3]]
    B -->|否| D[剩余目标:9, 路径:[]]
    C --> E[包含34?]
    E -->|是| F[剩余目标:-28, 剪枝]
    E -->|否| G[剩余目标:6, 路径:[3]]
    G --> H[包含4?]
    H -->|是| I[剩余目标:2, 路径:[3,4]]
    I --> J[包含12?]
    J -->|是| K[剩余目标:-10, 剪枝]
    J -->|否| L[剩余目标:2, 路径:[3,4]]
    L --> M[包含5?]
    M -->|是| N[剩余目标:-3, 剪枝]
    M -->|否| O[剩余目标:2, 路径:[3,4]]
    O --> P[包含2?]
    P -->|是| Q[剩余目标:0, 解:[3,4,2]]
    P -->|否| R[无解]
</mermaid>

== 数学表达 ==
子集和问题可以形式化为：
<math>
\exists S' \subseteq S \quad \text{使得} \quad \sum_{s \in S'} s = T
</math>

== 扩展阅读 ==
* [[动态规划]]解法：通过构建二维表格解决子集和问题，时间复杂度为<math>O(nT)</math>。
* [[近似算法]]：当问题规模较大时，可使用启发式方法寻找近似解。

== 总结 ==
子集和问题是一个经典的NP完全问题，可通过回溯法和分支限界法解决。虽然其最坏时间复杂度较高，但在实际应用中通过剪枝和优化仍能有效处理中小规模问题。理解该问题有助于掌握组合优化和算法设计的基本思想。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:回溯与分支限界]]