硬币问题

设有 个 整数 ，其中 。值 表示 种不同硬币的面额，其中这些面额的最大公约数为 1。则可以使用给定硬币表示的金额总和由下式给出

(1)

其中 是给出每种硬币使用数量的非负整数。如果 ，显然可以表示任何数量的钱 。然而，在一般情况下，只能产生某些数量 。例如，如果允许的硬币是 ，则不可能表示 和 3，尽管所有其他数量都可以表示。

确定函数 给出最大 且无解的情况，称为硬币问题，或有时称为换钱问题。给定问题的最大此类 称为弗罗贝尼乌斯数 。

结果

			(2)
			(3)

(Nijenhuis 和 Wilf 1972) 是数学界的共识。这种不可表示的金额总数由下式给出

(4)

两种面额为 和 的硬币的最大不可表示金额 总结如下。

2	3	1	4	7	17
2	5	3	4	9	23
2	7	5	5	6	19
2	9	7	5	7	23
3	4	5	5	8	27
3	5	7	5	9	31
3	7	11	6	7	29
3	8	13	7	8	41
3	10	17	7	9	47
4	5	11	7	10	53

对于三个数字，快速算法也是已知的，但是对于任意数量的数字的更一般问题，如果 是固定的 (Kannan 1992) 或 是可变的 (Ramírez-Alfonsín 1996)，则已知是 NP-hard 的。

对于 没有闭式解，尽管已知半显式解，该解允许快速计算值 (Selmer 和 Beyer 1978, Rödseth 1978, Greenberg 1988; Beck 和 Robins 2006)。 小 的值总结如下。

	1		5
	1		3
	1		3
	1		5
	3		2

对于 没有已知的闭式解。