子集和问题

子集和问题(英语:Subset sum problem),又称子集合加总问题,是计算复杂度理论密码学中一个很重要的问题。问题可以描述为:给一个整数集合,问是否存在某个非空子集,使得子集内中的数字和为某个特定数值。例:给定集合{−7, −3, −2, 5, 8},是否存在子集和为0的集合?答案是YES,因为子集{−3, −2, 5}的数字和是0。这个问题是NP完全问题,且或许是最容易描述的NP完全问题。

一个等价的问题是:给一个整数集合和另一个整数s,问是否存在某个非空子集,使得子集中的数字和为s。子集合加总问题可以想成是背包问题的一个特例。

动态规划解法

动态规划的方法,能够以伪多项式时间解决子集合加总问题。我们假定输入序列为:

x1, ..., xn

我们需要判断是否存在某个非空子集,使得子集中的数字和为0。我们序列中负数的和为N,正数的和为P。定义函数Q(i, s),它的涵义为:

是否存在x1, ..., xi的非空子集,使得子集中的数字和为s

子集合加总问题的答案即为Q(n, 0)。

显然,如果s < N或者s > P,则Q(i,s) = false,因此无需记录这些值。我们把Q(i, s)的值保存在数组中,其中1 ≤ i ≤ nN ≤ s ≤ P

接下来使用循环来填充数组。首先,对于N ≤ s ≤ P,设定

Q(1, s) := (x1 = s)

随后,对于i = 2, …, nN ≤ s ≤ P,设定

Q(i, s) := Q(i - 1, s) (xi = s) Q(i - 1, s - xi)

算法运行的总时间为O(n(P - N))。

对算法加以改动,即可返回和为0的子集。

在计算复杂度理论中,这种解法需要的时间并不算多项式时间,这是因为P - N输入大小并不成线性关系。原因在于输入大小仅仅取决于表达输入所需要的位元数。算法的时间复杂度同NP的值成线性关系,而它们的值与表达它们所需的位元数成幂关系。