主题
Search

子集和问题

下载 Mathematica Notebook下载 Wolfram Notebook

通常被称为子集和问题的问题有两个。

第一个（“给定和问题”）是找到一个整数列表的哪个子集具有给定的和的问题，这是一个整数关系问题，其中关系系数 a_i 是 0 或 1。

第二个（“相同和问题”）是找到一组 n 不同的正实数，使其具有尽可能多的具有相同和的子集（Proctor 1982）。

相同和问题由 Stanley（1980）使用代数几何的工具解决，对于 n 个数，答案由前 n 个正整数给出：{1,2,...,n}。Proctor（1982）给出了该结果的第一个初等证明。对于 {1,2,...,n}，具有相同和的子集的最大数量，对于 n=1、2、... 分别是 1、1、2、2、3、5、8、14、23、... (OEIS A025591)。类似地，对于 n=1、2、...，不同子集和的数量分别是 2、4、7、11、16、22、29、37、46、56、... (OEIS A000124)。例如，对于 n=3，{1,2,3} 的子集是

sumemptyset=0
(1)
1=1
(2)
2=2
(3)
3=3
(4)
1+2=3
(5)
1+3=4
(6)
2+3=5
(7)
1+2+3=6,
(8)

因此，出现频率最高的和是 3，它出现了两次，不同和的数量是 7。

给定和问题是 NP-完全 的。对于小规模情况，可以使用生成函数来解决。考虑从 M 个给定整数 {a_1,...,a_M} 中选择 m 个，使得它们的和等于 s 的方法数 c_(m,s)，并定义生成函数

G(x,y)=product_(k=1)^M(1+x^(a_k)y).
(9)

在 y 的幂展开后，这变为

G(x,y)=sum_(m=1)^MG_m(x)y^m.
(10)

但是，由于指数定律 x^mx^n=x^(m+n)，G_m(x) 正是所需的生成函数

G_m(x)=sum_(s)c_(m,s)x^s.
(11)

例如，考虑从集合 {1,2,3,4,5} 中选取 m 个对象的问题。生成函数 G(x,y) 是

G(x,y)=y^5x^(15)+(x^(14)+x^(13)+x^(12)+x^(11)+x^(10))y^4+(x^(12)+x^(11)+2x^(10)+2x^9+2x^8+x^7+x^6)y^3+(x^9+x^8+2x^7+2x^6+2x^5+x^4+x^3)y^2+(x^5+x^4+x^3+x^2+x)y+1.
(12)

因此，例如，选择 m=3 个对象具有生成函数

G_3(x)=sum_(s)c_(3,s)x^s
(13)
=x^(12)+x^(11)+2x^(10)+2x^9+2x^8+x^7+x^6,
(14)

因此，从整数 1 到 5 中选取三个整数，并使它们的和为 s=12、11、...、6 的方法数是 G_3(x) 的系数 c_(3,s)，即 1、1、2、2、2、1 和 1。这些解决方案总结在下表中。

s解决方案
6(1, 2, 3)
7(1, 2, 4)
8(1, 2, 5), (1, 3, 4)
9(1, 3, 5), (2, 3, 4)
10(1, 4, 5), (2, 3, 5)
11(2, 4, 5)
12(3, 4, 5)

Pólya (1956) 最初提出的一个很好的显式例子是，询问用一美元（使用 1 美分、5 美分、10 美分、25 美分和 50 美分）进行找零的方法数。答案 292 作为级数中 x^(100) 项的系数提供

sum_(n=0)^inftyP_kx^k=1/((1-x)(1-x^5)(1-x^(10))(1-x^(25))(1-x^(50)))
(15)

（Borwein 和 Bailey 2003，第 21 页）。

另请参阅

盈数, 网格阴影问题, 整数关系, 背包问题, 格基规约, 邮票问题, 伪完全数, Stöhr 序列, 怪数

使用 Wolfram|Alpha 探索

参考文献

Borwein, J. 和 Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 22-24, 2003.Coster, M. J.; LaMacchia, B. A.; Odlyzko, A. M.; 和 Schnorr, C. P. "An Improved Low-Density Subset Sum Algorithm." In Advances in Cryptology: EUROCRYPT '91 (Brighton, 1999) (Ed. D. W. Davis). New York: Springer-Verlag, pp. 54-67, 1992.Coster, M. J.; Joux, A.; LaMacchia, B. A.; Odlyzko, A. M.; Schnorr, C. P.; 和 Stern, J. "Improved Low-Density Subset Sum Algorithms." Comput. Complex. 2, 111-128, 1992.Ferguson, H. R. P. 和 Bailey, D. H. "A Polynomial Time, Numerically Stable Integer Relation Algorithm." RNR Techn. Rept. RNR-91-032, Jul. 14, 1992.Lagarias, L. C. 和 Odlyzko, A. M. "Solving Low-Density Subset Sum Problems." J. ACM 32, 229-246, 1985.Pólya, G. "On Picture-Writing." Amer. Math. Monthly 63, 689-697, 1956.Proctor, R. A. "Solution of Two Difficult Combinatorial Problems with Linear Algebra." Amer. Math. Monthly 89, 721-734, 1982.Schnorr, C. P. 和 Euchner, M. "Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems." In Fundamentals of Computation Theory: Proceedings of the 8th International Conference, Fct '91 Gosen, Germany, September 9-13, 1991. Berlin: Springer-Verlag, pp. 68-85, 1991.Sloane, N. J. A. Sequences A000124/M1041 和 A025591 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. "Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property." SIAM J. Alg. Disc. Math. 1, 168-184, 1980.

在 Wolfram|Alpha 中引用

子集和问题

引用为

Weisstein, Eric W. “子集和问题。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/SubsetSumProblem.html

主题分类