子集和问题中的所有子集

Question

我在解决子集和问题时遇到了困难。

给定一个整数集合(S)，需要计算出非空子集，其总和等于给定的目标值(T)。

示例： 给定集合S{4, 8, 10, 16, 20, 22} 目标值T = 52。

限制条件： 集合S的元素数量N限制为8。因此，由于N有一个较小的上限，可以接受NP时间复杂度的解决方案。 时间和空间复杂度并不是真正的问题。

输出:

可能的子集，其总和恰好等于T=52：

{10, 20, 22}

{4, 10, 16, 22}

Wiki和其他一些页面中提供的解决方案尝试检查是否存在这样的子集(YES/NO)。

它并不能真正帮助计算所有可能的子集，如上面的示例所述。

在这个链接中，动态规划方法只给出了一个这样的子集，但我需要所有这样的子集。

一个明显的方法是使用暴力计算所有2^N组合，但那将是我的最后手段。

我正在寻找一些编程示例（最好是C ++）或算法，可以计算出这样的子集并带有说明/示例。

- Arun

---

如果您有多个这样的目标（但是相同的数组），那么枚举甚至更好！您可以一次性获得所有可能的目标！因此，您只需枚举一次（每个数组）。 - Knoothe

嗨ritesh_nitw，N的上限为8（这意味着给定集合最多可能有8个元素，这是唯一的限制。 - Arun

@Arun：明确一点，您可以枚举一次，并为每个可能的目标存储子集列表。您可以使用哈希表（以目标为键）和8位整数列表（用于表示每个集合）作为值。下次获取目标查询时，只需查找哈希表并返回列表即可。 - Knoothe

@Knoothe，非常感谢您提供的宝贵意见。特别是“使用8位整数（来表示每个集合）”这个想法很好 :) - Arun

不用谢。用8位整数表示集合是一个众所周知的技巧（我相信其他人在他们的答案中也提到了这一点）。 - Knoothe

Answer 1

如果N<=8，为什么不采用2^n的解决方案呢？这只有256种可能性，非常快速。

- marcadian

---

即使N=30，仍然可以在1秒内完成。 - Mike T

@Mike T和marcadian，某种程度上我更倾向于采用蛮力方法 :) - Arun

Answer 2

当您构建子集和问题的动态规划表时，可以将其大部分初始化为以下内容（摘自问题中引用的维基百科文章）：

Q(i,s) := Q(i − 1,s) 或 (xi == s) 或 Q(i − 1,s − xi)

这将设置表元素为0或1。

这个简单公式不能让您区分那些可能会给您1的几种情况。

但是，您可以将表元素设置为一个值，该值将使您区分这些情况，类似于以下内容：

Q(i,s) := {Q(i − 1,s) != 0} * 1 + {xi == s} * 2 + {Q(i − 1,s − xi) != 0} *4 然后，您可以从最后一个元素遍历表。每个元素的值将告诉您是否从它有零条、一条或两条可能的路径以及它们的方向。所有路径都将给出所有相加为T的数字组合。这最多是2的N次方。

- Alexey Frunze

---

好主意！谢谢Alexey Frunze！ - Arun

@AlexeyFrunze，请详细说明如何获取所有子集？我有矩阵，但无法弄清如何使用它来生成所有可能的子集。另外，请问对于基本情况，即（i == 1），Q（i，s）应该是（xi == s）还是2 *（xi == s）？ - shivshnkr

@shivshnkr 子集是一条通过非零 Q(i,s) 单元格的路径，就像文章中描述的经典单解情况一样。如果按照我建议的计算 Q(i,s)，那么在每个单元格 Q(i,s) 处，当前路径可能会分叉成多条路径。您可以查看 Q(i,s) 中设置的位，从而知道下一步要去哪个单元格（们）。 - Alexey Frunze

@AlexeyFrunze 请查看这个矩阵并告诉我从哪里开始以及如何获取路径。如果 Q(i, s) = 5 或 4，应该选择哪条路径？http://codepad.org/47B9vJMe - shivshnkr

@shivshnkr，恐怕你需要先理解维基百科文章中解释的DP算法，因为在我看来，目前你似乎还没有理解，但如果你理解了，就不会问这个问题了。 - Alexey Frunze

Answer 3

只需要暴力解决。如果N限制在8以内，你的子集总数为2^8，仅有256个。他们给出约束条件是有原因的。

你可以将集合包含表示为二进制字符串，其中每个元素要么在集合中，要么不在集合中。然后，你可以通过增加二进制字符串（它可以简单地表示为一个整数）并使用位运算符 & 确定哪些元素在集合中或者不在集合中。一旦计数器增加到2^N，你就知道已经遍历了所有可能的子集。

- Mike T

Answer 4

最好的方法是使用动态规划方法。然而，正如你在问题中提到的那样，动态规划只回答是否存在子集和。

通过动态规划，您可以通过回溯输出所有解决方案。然而，生成所有有效组合的总时间复杂度仍为2^n。

因此，比2^n更好的算法几乎不可能。

UPD: 来自 @Knoothe 评论： 您可以修改 horowitz-sahni's 算法以枚举所有可能的子集。如果存在 M 这样的集合，其总和等于 S，则总时间复杂度为 O(N * 2^(N/2) + MN)

- Ritesh Kumar Gupta

---

@Knoothe：怎么做？你能详细说明一下吗？ - Ritesh Kumar Gupta

查询霍罗维兹-萨尼的子集和算法，其时间复杂度为O(sqrt(2^n))（即O(2^(n/2)))（可能漏掉了一个n的因子）。 - Knoothe

@Knoothe：阅读了以下讨论：http://en.wikipedia.org/wiki/Talk%3ASubset_sum_problem#Horowitz_and_Sahni ，仍然不确定Horowitz Sahini算法是否比DP更好。 - Ritesh Kumar Gupta

我并没有与动态规划进行比较。我只是在质疑这个说法：“比 2^n 更好几乎是不可能的”。你可以修改 Horowitz-Sahni 算法，以在 O(n * 2^(n/2) + mn) 的时间内枚举所有可能的子集（假设有 m 个这样的集合）。 - Knoothe

不客气 :-) 顺便说一下，我建议你不要链接到Talk:，因为那些只是一些随机人士之间关于子集和主维基页面编辑的讨论。我相信子集和主维基页面中有算法的提及，你应该链接到那里。 - Knoothe