主題
Search

郵票問題

考慮一個 集合 A_n={a_1,a_2,...,a_n} 由 n 個 正整數面值的郵票組成，並按 1=a_1<a_2<...<a_n 排序，使得 1=a_1<a_2<...<a_n。假設這些郵票要用於信封上，信封最多可以容納 h 張郵票。那麼，郵票問題的內容是確定最小的 整數 N_h(A_n)，它不能表示為 線性組合 sum_(i=1)^(n)x_ia_i，其中 x_i>=0 且 sum_(i=1)^(n)x_i<h。

如果沒有後一個限制，這個問題被稱為弗羅貝尼烏斯問題或弗羅貝尼烏斯郵票問題。

連續可能的郵資金額的數量由下式給出

n_h(A_n)=N_h(A_n)-1,
(1)

其中 n_h(A_n) 被稱為 h-範圍。

對於任意 A_n，當 n=2 和 3 時，存在精確解。當 n=2 時的解是

n_h(A_2)=(h+3-a_2)a_2-2
(2)

對於 h>=a_2-2。

n_h(2)=|_1/4(h^2+6h+1)_|,
(3)

(Stöhr 1955, Guy 1994)，其中 |_x_| 是 向下取整函式，其前幾個值是 2, 4, 7, 10, 14, 18, 23, 28, 34, 40, ... （OEIS A014616; Guy 1994, 第 123 頁）。

Hofmeister (1968, 1983) 表明，對於 h>=20，

n_h(3)=4/3(1/3h)^3+6(1/3h)^2+Ah+B,
(4)

其中 A 和 B 是 h (mod 9) 的函式，Mossige (1981, 1987) 表明

n_h(4)>=2.008(1/4h)^4+O(h^3)
(5)

(Guy 1994, 第 123 頁)。

Shallit (2002) 證明了 (區域性) 郵票問題在圖靈歸約下是 NP-hard 的，但如果 k 是固定的，則可以在多項式時間內解決。

一個相關的問題是，求不能表示為 a_i 的線性組合（可能假定 GCD(a_1,...,a_n)=1）的最大整數，有時被稱為 硬幣問題。

另請參閱

硬幣問題, 貪婪演算法, 和諧圖, 整數關係, 揹包問題, 郵票摺疊, Stöhr 序列, 子集和問題

使用 探索

參考文獻

Guy, R. K. "郵票問題。" §C12 in 數論中的未解問題，第 2 版 New York: Springer-Verlag, pp. 123-127, 1994.Hofmeister, G. "自然數中三元素極值基的漸近估計。" J. reine angew. Math. 232, 77-101, 1968.Hofmeister, G. "三元素極值基。" J. reine angew. Math. 339, 207-214, 1983.Hujter, M. and Vizvari, B. "具有三個變數的弗羅貝尼烏斯問題的精確解。" J. Ramanujan Math. Soc. 2, 117-143, 1987.Mossige, S. "計算郵票問題 h-範圍的演算法。" Math. Comput. 36, 575-582, 1981.Mossige, S. "關於極值 h-基 A_4。" Math. Scand. 61, 5-16, 1987.Mossige, S. "郵票問題：確定 k=4 的極值基問題的 h-範圍公式的 h-範圍的演算法。" Math. Comput. 69, 325-337, 2000.Nijenhuis, A. "“找零問題”的最小路徑演算法。" Amer. Math. Monthly 86, 832-835, 1979.Shallit, J. "區域性郵票問題的計算複雜度。" ACM SIGACT 33, 90-94, 2002.Sloane, N. J. A. 序列 A014616 in "整數序列線上百科全書"。Stöhr, A. "關於自然數序列的基的已解決和未解決的問題 I, II。" J. reine angew. Math. 194, 111-140, 1955. Wagon, S. "貪婪硬幣。" http://library.wolfram.com/infocenter/MathSource/5187/.

在 中被引用

郵票問題

請引用為

Weisstein, Eric W. "郵票問題。" 來自 —— 資源。 https://mathworld.tw/PostageStampProblem.html

主題分類