子集和問題
此條目沒有列出任何參考或來源。 (2015年1月22日) |
子集和問題(英語: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 ≤ n且N ≤ s ≤ P。
接下來使用循環來填充數組。首先,對於N ≤ s ≤ P,設定
- Q(1, s) := (x1 = s)
隨後,對於i = 2, …, n和N ≤ s ≤ P,設定
- Q(i, s) := Q(i - 1, s) 或 (xi = s) 或 Q(i - 1, s - xi)
算法運行的總時間為O(n(P - N))。
對算法加以改動,即可返回和為0的子集。
在計算複雜度理論中,這種解法需要的時間並不算多項式時間,這是因為P - N同輸入大小並不成線性關係。原因在於輸入大小僅僅取決於表達輸入所需要的位元數。算法的時間複雜度同N與P的值成線性關係,而它們的值與表達它們所需的位元數成冪關係。