子集和問題:修订间差异
外观
删除的内容 添加的内容
Symplectopedia(留言 | 贡献) iw |
小 使用DisamAssist清理消歧義連結:集合(改連結至集合 (数学); 改連結至集合 (数学))。 |
||
(未显示16个用户的19个中间版本) | |||
第1行: | 第1行: | ||
{{unreferenced|time=2015-01-22T03:38:44+00:00}} |
|||
'''子集 |
'''子集和問題'''({{lang-en|'''Subset sum problem'''}}),又称'''子集合加總問題''',是[[計算複雜度理論]]和[[密碼學]]中一個很重要的問題。问题可以描述为:給一個整數[[集合 (数学)|集合]],問是否存在某個非空[[子集]],使得子集内中的數字和為某个特定数值。例:給定集合{−7, −3, −2, 5, 8},是否存在子集和为0的集合?答案是YES,因為[[子集]]{−3, −2, 5}的數字和是0。這個問題是[[NP完全]]问题,且或許是最容易描述的NP完全問題。 |
||
一個等價的問題是:給一個整數[[集合]]和另一個整數''s'',問是否存在某個非空[[ |
一個等價的問題是:給一個整數[[集合 (数学)|集合]]和另一個整數''s'',問是否存在某個非空[[子集]],使得子集中的數字和為''s''。子集合加总问题可以想成是[[背包問題]]的一個特例。 |
||
==动态规划解法== |
|||
用[[动态规划]]的方法,能够以[[伪多项式时间]]解决子集合加总问题。我们假定输入序列为: |
|||
: ''x''<sub>1</sub>, ..., ''x<sub>n</sub>'' |
|||
我们需要判断是否存在某个非空子集,使得子集中的数字和为0。我们序列中负数的和为''N'',正数的和为''P''。定义函数''Q''(''i'', ''s''),它的涵义为: |
|||
: 是否存在''x''<sub>1</sub>, ..., ''x<sub>i</sub>''的非空子集,使得子集中的数字和为''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''<sub>1</sub> = ''s'') |
|||
随后,对于''i'' = 2, …, ''n''和''N ≤ s ≤ P'',设定 |
|||
: ''Q''(''i'', ''s'') := ''Q''(''i'' - 1, ''s'') '''或''' (''x<sub>i</sub>'' = ''s'') '''或''' ''Q''(''i'' - 1, ''s'' - ''x<sub>i</sub>'') |
|||
算法运行的总时间为''O''(''n''(''P'' - ''N''))。 |
|||
对算法加以改动,即可返回和为0的子集。 |
|||
在计算复杂度理论中,这种解法需要的时间并不算多项式时间,这是因为''P'' - ''N''同''输入大小''并不成线性关系。原因在于输入大小仅仅取决于表达输入所需要的位元數。算法的时间复杂度同''N''与''P''的值成线性关系,而它们的值与表达它们所需的位元數成幂关系。 |
|||
[[Category:NP完全问题]] |
|||
[[Category:計算複雜性理論]] |
[[Category:計算複雜性理論]] |
||
[[Category:数学问题]] |
[[Category:数学问题]] |
||
[[ar:مسألة مجموع المجموعات الجزئية]] |
|||
[[de:Untermengensumme]] |
|||
[[en:Subset sum problem]] |
|||
[[es:Problema de la suma de subconjuntos]] |
|||
[[fa:مسئله جمع زیرمجموعهها]] |
|||
[[fr:Problème de la somme de sous-ensembles]] |
|||
[[ko:부분집합 합 문제]] |
|||
[[ja:部分和問題]] |
|||
[[pl:Problem sumy podzbioru]] |
2023年2月24日 (五) 00:35的最新版本
此條目没有列出任何参考或来源。 (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的值成线性关系,而它们的值与表达它们所需的位元數成幂关系。