子集和问题和回溯算法

2022-04-20 IT知识

子集和问题是找到给定集合S =（S1 S2 S3 … Sn）的子集, 其中集合S的元素是n个正整数, 其方式为s’ ∈S和子集的元素等于一些正整数“ X”。
【子集和问题和回溯算法】子集和问题可以通过使用回溯方法来解决。在这个隐式树中是一个二叉树。选择树的根的方式表示尚未对任何输入做出决定。我们假设给定集合的元素按升序排列：

S1 ≤ S2 ≤ S3... ≤ Sn

根节点的左子节点指示我们必须包含集合“ S”中的“ S1”, 而根节点的右子节点指示我们必须执行“ S1”。每个节点存储部分解决方案元素的总数。如果在任何阶段总和等于“ X”, 则搜索成功并终止。
只有当两个不等式之一存在时, 树中的死角才会出现：

s’ 的总和太大, 即

s'+ Si + 1 > X

s’ 的总和太小, 即

文章图片
示例：给定集合S =（3, 4, 5, 6）和X = 9。使用回溯方法获得子集总和。
解：

Initially S = (3, 4, 5, 6) and X =9.S'= (?)

子集和问题的隐式二叉树如图所示：

文章图片
节点内的数字是特定级别上部分解决方案元素的总和。
因此, 如果我们的部分解元素之和等于正整数“ X”, 则搜索将终止, 或者如果需要获得所有可能的解, 则搜索将继续。

推荐阅读

上一篇：哈密??顿回路问题和回溯法

下一篇：N皇后问题和回溯算法