自助设备配钞算法初探.doc

自助设备配钞算法初探摘要目前自助设备配钞算法技术，一种面额容易处理，两种或两种面额以上，一般采用穷举法，穷举法肯定不是最优算法，又由于各面额出钞张数的各类限制，如各面额可用钞票数限制、系统预设的出钞原则限制，还有可能是用户对各面额出钞张数的限制，使得穷举法的开销比较大。本文提供一种直接求解多元一次正整系数方程的通解方法，利用各面额出钞张数的各类限制，直接对通解中的自由因子进行范围限制，最终成功得到可行的配钞方案。本配钞方法直观、高效、快速、严谨，不必要使用穷举法，就很快找出所有配钞方案，具有配钞时间少，配钞效率高等优点。1前言金融自助设备配钞是指对自动柜员机中各个钞箱中不同面额的钞票数量进行统筹管理。一般地，金融自助设备装有至少一个钞箱，至少有一种面额，每一个钞箱装有一定数量的相同面额的钞票。在出钞时，需要对用户输入金额按照各种面额进行配钞，在优先满足用户需求的同时，也要兼顾加钞维护，因此，每次出钞进行配钞，需要根据用户输入金额和钞箱可用钞票生育情况，进行综合管理。目前主要有五种配钞原则： 各钞箱均空法：各个面额的钞票以近乎相同的概率被清空。各钞箱平均法：按照各个面额张数近乎相等的配钞方案进行出钞。大面额优先法：优先出面额大的，按照该种方案出钞，但总张数不一定最小。小面额优先法：按照总张数最多的配钞方案进行出钞。总张数最小法：按照各面额出钞总张数最小的配钞方案进行出钞。2配钞建模本文提供了一种金融自助设备配钞方法，利用直接求解一元多次整系数方程的整数解的通解办法，得出一元多次方程的整数解的通解办法，然后根据各面额配钞数额必须大于零，且小于自助设备该种面额的剩余可用钞票数，且不小于用户要求的各面额需求张数，求解出通解公式中自由因子的限定范围，从而很快得出了所有的配钞方案数。最后依据自助服务系统的配钞原则（均空法、平均法、最小张数法、最大面额优先法、最小面额优先法），得出一种最优化的配钞方案。根据本文提供的一种金融自助设备配钞方法，不妨假设自助设备上有n种面额，各个面额的面额值从小到大依次为，自助设备上各个面额对应的可用的张数，用户要求的各面额最低需求张数，现需要对配钞金额为M进行配钞，设各个面额的配钞张数为，则有关系式：，即，其中。3配钞求解本文所述的金融自动设备配钞方法，包括如下步骤：S2：判断配钞金额是否不大于所述金融自助设备中钞箱剩余金额总数，是则转步骤S3；否则配钞失败，结束。S3：求出各面额值的最大公约数，判断各面额值的最大公约数是否可以整除配钞金额，是则转步骤S4；否则配钞失败，结束。S4：判断两面额值的最大公约数是否大于1，是则将两边同除以，得到型如元一次整系数不定方程，其中，且；否则保持原样。S5：元一次整系数不定方程中，如果中存在两个互质的系数1，是则转S6，否则按照下述方法转化为具有两个互质系数的等价的元一次方程：由于的绝对值都大于1，找出绝对值最小的一个系数，且不妨设，则其他系数可以表示为：.此时原方程可转化为：.若中有某两个互质，则转步骤S6；若中任何两个都不互质，再次找出其中最小的系数，将其他系数用该最小系数表示，再次进行转化，一直到有两个互质为止。如可以转化为，令，则，其中y的系数4与z的系数3 互质了。 S6：多元一次方程等价转换成型如的至少具有两个互质的系数的多元一次方程，不妨设，那么。若的一个特解为，其中特解求解方法见前述S4两种面额配钞法。S7：元一次不定方程（其中）的通解公式为： 其中。于是就可以求出的解。如可以转化为，令，则，至此，已经将转换为具有两个互质系数的等价的，其中其中的系数4与的系数3 互质了。 因此只要求解出的正整数解，就相应的可以求出的正整数解了。由于的通解为：，则的通解为：又因为于是的通解为由此可见，元一次不定方程在有解前提下，如存在两个系数的最大公约数是1，则它的通解中含有个参变量，其中的个参变量都可以取原来的变元。S8：根据（为用户对各面额的最低需求张数，为各面额的剩余可用钞票数），由此可以求出整数的取值范围。S9：根据配钞原则，进一步限制的值，根据配钞原则的不同，可分为以下几种情况，在,范围内确定的取值：S51）各钞箱平均法，此时，有取最小值；S52）各钞箱均空法，此时，有取最小值；S53）最小总张数法，尽可能小，即求；S54）最小面额优先法，如果是所有面额最小者，尽可能大；S55）最大面额优先法，如果是所有面额最大者，尽可能大。4配钞举例假设自助设备配备有四种面额100、50、20、15，即。剩余可用钞票分别为：。如果用户输入金额为1565，由于100、50、20、15的最大公约数为5，根据，两边同除5，得到，由于互质，所以方程变为二元一次方程：，由于的通解为：，则的通解为：， 由和得到可得到，确定的取值范围为。1）如果是平均出钞法，有，根据有最小，即。得到为所求配钞方案（8，9，9，9）。2）如果是均空法，有，根据取最小值，得到为所求配钞方案，各面额原有（15，10，18，20），出钞后剩余为（6，6，6，5）。3）如果是张数最小法，有尽可能小，即尽可能小，得到最小张数为17张，为所求配钞方案（15，1，0，1）。4）如果是最大面额优先法，有尽可能大，其次尽可能大，再次尽可能大，得到为所求配钞方案（15，1，0，1）。5）如果是最小面额优先法，有尽可能大，其次尽可能大，再次尽可能大，得到为所求配钞方案（5，10，14，19），各面额原有（15，10，18，20），出钞后各面额剩余（10，0，4，1）。5结论本文提供的配钞方法，在自助柜员机每次清钞完，或某种面额的钞箱卡钞或清空导致自助柜员机不能提供该种面额后，进行配钞算法的配置，在此情况下自助柜员机的钞箱个数、面额种数也已确定。配钞计算时，通过快速求解出所有可行的配钞方法，在