最少钱币数量的计算与钱币面额的确定

肖红德

XIAO Hongde

河南大学 数学与统计学院，河南 开封 475004

School of Mathematics and Statistics,Henan University,Kaifeng,Henan 475004,China

1 概述

计算机作为一种工具，在处理需要大量计算的场合发挥着巨大的作用，在解决需要大量计算的问题上，一般涉及两方面：一方面是需要设计相关的算法尽量降低算法的复杂度；另一方面在通过计算机语言进行实现的时候还需要对算法进行优化，从而使得在解决问题时尽可能地提高效率。本文通过结合埃拉托色尼筛法、迪杰斯特拉算法和图的广度优先遍历算法的思想，提出了一种用来计算平均钱币数量的快速算法，即最少钱币数量筛法，并通过计算给定范围的三种钱币组合计算其平均钱币数量，与动态规划算法相比，计算速度明显加快，与贪心算法相比，计算结果更好。对于给定范围、给定钱币种类，如何确定钱币组合这个问题，本文通过对不同钱币之间数值特征的分析，给出了各个数值满足的拟合曲线，从而在寻找最佳钱币种类组合上使得算法的时间复杂度大大降低，程序的运算时间大大缩短。文中选择MATLAB R2017b作为运行环境，针对上述提出的两种算法进行了具体实现。

2 相关研究

关于纸币面值的组合情况研究，Jeffrey已经给出了相关研究结果，见参考文献[1]。其结果如表1所示。

表2给出的货币最佳发行方案是通过动态规划算法计算出来的。动态规划有关的算法见参考文献[2-4]，本文计算的结果与Jeffrey给出的结果不同，原因是Jeffrey计算的范围包括1但不包括100，且按照100进行平均。如果本文也按照这样的方法进行计算，则得到的结果与Jeffrey相同。其他钱币方案中平均钱币数量的计算与此类似。

对于给定某个值，在计算其所需要最少数量钱币组合的时候，如果钱币种类多于两种，尽管贪心算法计算速度比较快，却一般不能使用贪心算法进行计算，贪心算法的相关内容见参考文献[2，5-6]。这是由于对于贪心算法计算出来的结果，在某些组合下不能得到最优结果。比如，使用贪心算法，对于1-5-16-23-33这种组合，在计算32最优组合方案时，使用贪心算法计算的结果是32=23×1+5×1+1×4，一共需要6个钱币，而如果使用动态规划计算结果为32=16×2，一共需要2个钱币。因此，贪心算法在有些情况下得到的不是最优钱币组合。

对于钱币种类的确定还有很多其他相关研究，比如参考文献[7]研究了有关增加某个钱币面额的数值分析和确定方法。

3 确定平均钱币数量的快速计算方法——最少钱币数量筛法

借助埃拉托色尼筛法（见参考文献[8-10]）、迪杰斯特拉算法（见参考文献[11-13]）、图的广度优先遍历算法（见参考文献[11]）的思想，提出一种新的对于给定钱币种类之后在一定范围内进行快速计算最少需要钱币数量的算法，以下称之为最少钱币数量筛法。

最少钱币数量筛法实现的具体计算过程如下：

首先令W为给定数值的钱币组合，V为一定范围内的数据集合，cur:=1，cur值用于表示当前能够计算出来的钱币值所需要的最少钱币数量，把需要计算的钱币范围V分成两组：

（1）S，已求出最小钱币数量的钱币集合（初始时为0）；

（2）T:=V-S，尚未确定最小钱币数量的钱币集合（初始时为V的全集）。

然后进行以下计算过程：

（1）将S中新加入的每一个数加上W中的每一个数（初始时认为新加入的数是0），若得到的数在T中，则将其加入到S中，其钱币数量记为cur；

（2）修改集合T，去除（1）中S新加入数的集合；

（3）将cur值加1，即cur:=cur+1；

（4）重复执行（1）～（3），直到集合T为空。

4 对任意数量范围内通过构造钱币组合确定平均钱币数量

对于不同钱币数量最优组合的确定，给定钱币范围[1,n]，N种钱币组合的情况，可以构造(n0/N,n1/N,…,n(N-1)/N)这种按照等比数列规律出现的一组数字，这里用(1,a,…,aN-1)表示，其中a=n1/N，为了表达方便，假设其为整数。对于这样的构造方案，其好处是在计算其平均钱币数量时可以使用贪心算法来得到某个数值的钱币数量，这样方便统计其平均钱币数量。

表1 Jeffrey的货币最佳发行方案

表2 本文计算出来的货币最佳发行方案

由上面的构造组合可以得出以下结论：钱币组合方案的最佳组合不高于构造组合(1,a,…,aN-1)。对于这样的构造组合，下面通过计算得到平均钱币数量。

f(1)=最大钱币值为1的钱币数值数量

f(2)=最大钱币值为a的钱币数值数量

…

f(N)=最大钱币值为aN-1的钱币数值数量

则有：

最后+1表示的是aN，即n这一个数的表示。从而有：

从而可以推出总数量为：

进而说明上述计算的钱币数值包含钱币范围内的所有钱币数值。

对于通过上述方案构造的钱币组合，可以计算其平均钱币数量，具体计算过程如下：令t()

i=由所有最大钱币面额为ai-1的钱币组合钱币数量之和，其中1≤i≤N。则有：

最后+a表示的是aN,即n这一个数的表示，需要的钱币数量为a。

因此，需要的平均钱币数量为：

对于三种钱币的组合，通过遍历计算得到的平均钱币数量最优值和上述构造方法得到的平均钱币数量比值大约在（0.95，1.00）之间，并且随着范围的增大，比值也趋向于增大。

5 构造组合和最优组合的对比

对于最优组合的设计，需要将第一个钱币固定为1，其他钱币种类需要进行遍历得到。对于钱币种类为2的钱币组合，通过第4章关于平均钱币数量的计算比较容易得到，第二个钱币值是关于a0.5的向上取整或向下取整的整数，见表3和图1。对于钱币种类大于2的钱币种类的确定，需要通过遍历方式得到。

表3 两种钱币组合在最优钱币组合下平均钱币数量表

图1 两种钱币组合平均数量理论值与实际值对比

图1说明：蓝线表示在最优钱币组合下的平均钱币数量图，绿色表示通过构造钱币组合得到的平均钱币数量理论值，其公式为y=x1/2-1+x-1/2，其中x表示钱币范围，y表示平均需要的钱币数量。通过图1可以发现，对于两种钱币的组合，理论值和实际值基本完全吻合。

以下讨论如何确定钱币的最优组合问题。

对于三种钱币的最优钱币种类确定问题，当取值范围很大时，需要遍历次数太多，因此需要尽可能缩小遍历次数。通过计算可知，对于113≤n≤253的情况，第一个数是固定的1，第二个数通过已有例子的模拟（见图4和图5）可以确定其曲线拟合表达式为n1040/2711+1255/452，拟合值与真实值的差值在区间[-8197/521,8107/702]上，第三个数的曲线拟合表达式为n25391/38087+1235/478，拟合值与真实值的差值在区间[-8197/521,8107/702]上。第二个数的平方与第三个数的比值处于(2.5,3.2)之间。通过对第二个数和第三个数以及第二个和第三个数之间关系的限定，可以大大减少遍历次数。

曲线拟合的实现是按照最小二乘法原理进行实现的，有关曲线拟合的MATLAB实现和最小二乘法原理见参考文献[14-18]。

对于三种钱币的最优钱币组合，最终所得结果见表4和图2。

表4 三种钱币组合在最优钱币组合下平均钱币数量表

图2 三种钱币组合平均数量理论值与实际值对比

图2说明：蓝色表示在最优钱币组合下的平均钱币数量图，绿色表示通过构造钱币组合得到的平均钱币数量图，其公式为y=3×a/2-3/2+a-2，其中a=n1/3。由图2可知，构造值比真实值要高，真实值与构造值之比主要集中于0.96～0.97之间。

以下是计算3个最优钱币组合与数值范围n相互之间关系的模拟效果图。图3中横轴表示数值范围n，纵轴表示第二个数的平方与第三个数的比值。第二个数和第三个数之间差值的计算可以通过该结果进行估计。

第二个参数和第三个参数之间的关系可以通过图3的模拟结果进行估计。第二个数的数量级可以通过图4的模拟结果进行估计。第三个数的数量级可以通过图5的模拟结果进行估计。

图3 三种钱币组合第二个数与第三个数的关系

图4 三种钱币组合第二个钱币值的拟合效果图

图3说明：在该图中，最大值为1296/409（约为3.1687），最小值为361/139（约为2.5971）。

图5 三种钱币组合第三个钱币值的拟合效果图

图4说明：蓝色曲线表示第二个钱币种类的真实值，绿色表示第二个钱币种类的曲线拟合值，其拟合曲线方程为y=x1040/2711+1255/452，其中x表示钱币的范围，y表示第二个钱币种类的曲线拟合值，拟合值和真实值的最大差值为1216/985（约为1.2345），最小差值为-853/475（约为-1.7958）。

图5说明：蓝色曲线表示第三个钱币种类的真实值，绿色表示第三个钱币种类的曲线拟合值，其拟合曲线方程为y=x25391/38087+1235/478，其中x表示钱币的范围，y表示第三个钱币种类的曲线拟合值，拟合值和真实值的最大差值为8107/702（约为11.5484），最小差值为-8197/521（约为-15.7332）。

四种以及更多种钱币组合的确定更为复杂。与三种钱币组合的确定类似，第一个数是固定的1，后面的数值需要通过遍历或者通过已经找出的数值发现数值规律，在规律的基础上进行限制，这里不再讨论。

6 结论

本文提出了一种对于给定钱币组合在给定范围情况下快速计算需要的平均钱币数量的方法，对于三种钱币组合，给出了一种确定钱币范围的计算方法，并在此基础上对钱币种类的范围进行了限制，其好处是可以大大减少对于最佳钱币组合的搜索范围。