主题
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 序列, 子集和问题

使用 Wolfram|Alpha 探索

参考文献

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/.

在 Wolfram|Alpha 中被引用

邮票问题

请引用为

Weisstein, Eric W. "邮票问题。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/PostageStampProblem.html

主题分类