主題
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 序列, 怪數

使用 探索

參考文獻

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.

在 中引用

子集和問題

引用為

Weisstein, Eric W. “子集和問題。” 來自 Web 資源。 https://mathworld.tw/SubsetSumProblem.html

主題分類