algorithm - 子集和问题算法的工作

Question

谁能解释一下子集和算法是如何工作的？ (我看到了 Cormen 在 Intro to algo 中给出的算法，但我不明白它是如何工作的)

Answer 1

有 2^n-1 个子集需要考虑(不考虑空集)。

平均而言，这 2^n 个子集中的每个子集都有 O(n) 个元素。所以你最终会进行 n*2^n 次计算来解决问题。

有一些可能的加速，但没有什么能绕过 2^n。

如果元素的绝对大小很小(并且是离散的)，您可以启动一个表来指示特定总和是否可达，然后将元素添加到表中的这些“位置”。

首先，制作表格。它的范围将从所有负数的总和到所有正数的总和。 (通过这种方式，您不会得到任何超出表格范围的金额。)

然后，将“0”标记为可达。

然后，对于每个号码，对于您 table 上每个可到达的号码，添加该号码。因此，如果您的第一个数字是 2，则将“2”标记为可达。然后，如果得到-3，则将“-3”和“2-3=-1”标记为可达。依此类推，直到用完数字。表中标记为可达的每个部分确实是可达的；您添加了一些数字以到达那里!