子集和問題

此條目没有列出任何参考或来源。 (2015年1月22日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。

子集和問題（英語：Subset sum problem），又称子集合加總問題，是計算複雜度理論和密碼學中一個很重要的問題。问题可以描述为：給一個整數集合，問是否存在某個非空子集，使得子集内中的數字和為某个特定数值。例：給定集合{−7, −3, −2, 5, 8}，是否存在子集和为0的集合?答案是YES，因為子集{−3, −2, 5}的數字和是0。這個問題是NP完全问题，且或許是最容易描述的NP完全問題。

一個等價的問題是：給一個整數集合和另一個整數s，問是否存在某個非空子集，使得子集中的數字和為s。子集合加总问题可以想成是背包問題的一個特例。

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

x₁, ..., x_n

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

是否存在x₁, ..., x_i的非空子集，使得子集中的数字和为s

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

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

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

Q(1, s) := (x₁ = s)

随后，对于i = 2, …, n和N ≤ s ≤ P，设定

Q(i, s) := Q(i - 1, s) 或 (x_i = s) 或 Q(i - 1, s - x_i)

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

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

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