金融自助終端配鈔算法研究

謝衛(wèi)平 王慶華 謝興鋒

（深圳怡化電腦股份有限公司，廣東 深圳 518026）

[關(guān)鍵字] ATM；配鈔算法；均空法；平均法；混合面額鈔箱

1 引言

金融自助終端配鈔是指對(duì)ATM機(jī)芯中各個(gè)鈔箱中不同面額的鈔票數(shù)量進(jìn)行統(tǒng)籌管理。一般地，金融自助設(shè)備裝有至少一個(gè)鈔箱，至少有一種面額，每一個(gè)鈔箱裝有一定數(shù)量的相同面額的鈔票，設(shè)備出鈔不但需要考慮滿足用戶的取款需求，同時(shí)還需要兼顧考慮維護(hù)人員的加鈔維護(hù)需求，因此，每次設(shè)備出鈔時(shí)都需要根據(jù)用戶輸入金額進(jìn)行配鈔，還需要對(duì)鈔箱可用鈔票剩余情況進(jìn)行綜合管理。

在自助設(shè)備技術(shù)領(lǐng)域主要有如下六類配鈔原則：

(1)均空法：各個(gè)面額的鈔票以近乎相同的概率被清空；

(2)平均出鈔法：按照各個(gè)面額張數(shù)近乎相等的配鈔方案進(jìn)行出鈔；

(3)大面額優(yōu)先法：優(yōu)先出面額大的，按照該種方案出鈔，但總張數(shù)不一定最小；

(4)小面額優(yōu)先法：按照總張數(shù)最多的配鈔方案進(jìn)行出鈔；

(5)最小總張數(shù)法：按照各面額出鈔總張數(shù)之和最小的配鈔方案進(jìn)行出鈔；

(6)最大總張數(shù)法：按照各面額出鈔總張數(shù)之和最大的配鈔方案進(jìn)行出鈔。

目前，絕大部分自助終端產(chǎn)品采用窮舉法技術(shù)來(lái)實(shí)現(xiàn)以上配鈔原則，效率太低，弊端明顯。也有部分廠商對(duì)窮舉法進(jìn)行了改進(jìn)，如根據(jù)貨幣面額的數(shù)值特征進(jìn)行組合求解，雖提高了配鈔效率但不具有通用性，又如文獻(xiàn)[1]根據(jù)小于所有面額公倍數(shù)的殘值利用窮舉法進(jìn)行二次配鈔的方法，存在不能快速求出所有可行的配鈔方案，算法具有不確定性的問(wèn)題。其他的一些算法，如文獻(xiàn)[2]提供的配鈔方法時(shí)間復(fù)雜度高，難以發(fā)現(xiàn)各可行配鈔方案之間的邏輯關(guān)系并進(jìn)行優(yōu)選。

本文對(duì)現(xiàn)有配鈔算法存在的一些技術(shù)問(wèn)題進(jìn)行了針對(duì)性研究，并提出了一種新的配鈔算法，解決了現(xiàn)有配鈔算法的效率性問(wèn)題和不確定性問(wèn)題。

2 配鈔數(shù)學(xué)建模

金融自助設(shè)備配鈔可分為單一面額鈔箱配鈔和混合面額鈔箱配鈔兩大類。

2.1 單一面額鈔箱配鈔

假設(shè)自助設(shè)備上有n種面額，各個(gè)面額的面額值從小到大依次為A1、A2……An，自助設(shè)備上各個(gè)面額A1、A2……An對(duì)應(yīng)的可用的張數(shù)S1、S2……Sn，用戶要求的各面額最低需求張數(shù)B1、B2……Bn，現(xiàn)需要對(duì)配鈔金額為M進(jìn)行配鈔，設(shè)各個(gè)面額 的 配 鈔 張 數(shù) 為 X1、X2……Xn，則 有 關(guān) 系 式 ：A1X1+A2X2+…+AnXn=M ，即

其中 B1≤X1≤S1,B2≤X2≤S2…Bn≤Xn≤Sn

2.2 混合面額鈔箱配鈔

假設(shè)自助設(shè)別配備有m個(gè)混合面額鈔箱，Ai表示第i個(gè)混合面額鈔箱，Aij表示第i個(gè)混合面額鈔箱中第j張鈔票，表示第i個(gè)混合面額鈔箱中前k張鈔票的總額。

設(shè)單一面額鈔箱為B，Bi表示第i個(gè)單一面額鈔箱。設(shè)配鈔結(jié)果為：第i個(gè)混合面額鈔箱出鈔Xi張鈔票，第i個(gè)單一面額鈔箱出鈔Yi張鈔票。設(shè)所述的配鈔總額為Total，自助設(shè)備有n個(gè)混合面額鈔箱和m個(gè)單一面額鈔箱，則有

即

假設(shè)對(duì)于第i個(gè)混合面額鈔箱，其前j張鈔票的總額為Sij，則有，其中Aik表示第i個(gè)混合鈔箱中第k張鈔票的面額。

則一個(gè)序號(hào)為i，總計(jì)有p張剩余鈔票的混合鈔箱，可得到一個(gè)數(shù)組：Si1,Si2…Sik,Si(k+1)…Sip，其中 Si(k+1)=Sik+Ai(k+1)。

3 配鈔求解

3.1 單一面額鈔箱配鈔計(jì)算

單一面額鈔箱的配鈔方法如下：

(1)判斷配鈔金額是否不大于所述金融自助設(shè)備中鈔箱剩余金額總數(shù)，是則轉(zhuǎn)步驟(2)；否則配鈔失敗，結(jié)束。

(2)求出各面額值的最大公約數(shù)，判斷各面額值的最大公約數(shù)是否可以整除配鈔金額，是則轉(zhuǎn)步驟(3)；否則配鈔失敗，結(jié)束。

(3)判斷兩面額值的最大公約數(shù)gcd(A1,A2…An)是否大于1，是則將兩邊同除以 gcd(A1，A2…An)，得到型如n元一次整系數(shù)不定方，其中g(shù)cd(a1，a2，…，an)=1，且 M=m·gcd(A1,A2…An)；否則保持原樣。

由于 a1，a2，…，an的絕對(duì)值都大于1，找出絕對(duì)值最小的一個(gè)系數(shù)，且不妨設(shè)a1＞0，則其他系數(shù)可以表示為：ai=kia1+ri,0≤ri＜a1(i=2,3,…,n)。此時(shí)原方程可轉(zhuǎn)化為：a1(x1+k2x2+…+knxn)+r2x2+r3x3+…+rnxn=M。若a1，r2，r3，…，rn中有某兩個(gè)互質(zhì)，則轉(zhuǎn)步驟(5)；若a1，r2，r3，…，rn中任何兩個(gè)都不互質(zhì)，再次找出其中最小的系數(shù)，將其他系數(shù)用該最小系數(shù)表示，再次進(jìn)行轉(zhuǎn)化，一直到有兩個(gè)互質(zhì)為止。

其中t,Y3,Y4,…,Yn∈Z。于是就可以求出的解。

(7)根據(jù)B1≤X1≤S1,B2≤X2≤S2…Bn≤Xn≤Sn(B1,B2…Bn為用戶對(duì)各面額的最低需求張數(shù)，S1、S2……Sn為各面額的剩余可用鈔票數(shù))，由此可以求出整數(shù)t的取值范圍。

(8)根據(jù)配鈔原則，進(jìn)一步限制X1、X2……Xn的值，根據(jù)配鈔原則的不同，可分為以下幾種情況，在[t1,t2]范圍內(nèi)確定t的取值：

a)平 均 出 鈔 法 ，此 時(shí) X1≈X2≈…≈Xn，有取最小值；

b)均 空 法 ，此 時(shí) X1-S1≈X2-S2≈…≈Xn-Sn，有取最小值；

e)最小面額優(yōu)先法，如果Ai是所有面額最小者，Xi盡可能大；

f)最大面額優(yōu)先法，如果Ai是所有面額最大者，Xi盡可能大。

g)如果是平均出鈔法，有 X1≈X2≈X3≈X4，根據(jù)有

h)如果是均空法，有 X1-S1≈X2-S2≈X3-S3≈X4-S4，根據(jù)取最小值。

i)如果是張數(shù)最小法，有(X1+X2+X3+X4)盡可能小。

j)如果是張數(shù)最大法，有(X1+X2+X3+X4)盡可能大。

k)如果是最大面額優(yōu)先法，有X1盡可能大，其次X2盡可能大，再次X3盡可能大。

l)如果是最小面額優(yōu)先法，有X4盡可能大，其次X3盡可能大，再次X2盡可能大。

m)單一面額鈔箱的配鈔方案的總種數(shù)，還可以采用組合數(shù)學(xué)中母函數(shù)（生成函數(shù)）求解，需要用到泰勒基數(shù)展開(kāi)式，可參考文獻(xiàn)[6]相關(guān)章節(jié)，在此不復(fù)贅述。

3.2 混合面額鈔箱的配鈔計(jì)算

混合面額鈔箱配鈔是指：一個(gè)或多個(gè)鈔箱同時(shí)存放有兩種不同面額情況下的配鈔?；旌厦骖~鈔箱配鈔分為兩種情況：混合面額鈔箱優(yōu)先法、單一面額鈔箱優(yōu)先法。

3.2.1 混合面額鈔箱優(yōu)先法

假設(shè)自助設(shè)別配備有m個(gè)混合面額鈔箱，其要求出鈔的優(yōu)先順序?yàn)锳1、A2……Am。假設(shè)Ai鈔箱有Xi張剩余鈔票，假設(shè)配鈔過(guò)程中混合鈔箱的出鈔數(shù)組為D，D1為第一張要出鈔的鈔票，Di為第i張要出鈔的鈔票，則對(duì)于 Ai(1≤i≤m)，有

得到Am的數(shù)組 Sm：Sm1、Sm2…Sm,Xm。

混合面額鈔箱優(yōu)先法配鈔算法如下：

(1)令j=1，殘值Cj=Total。

(2)在混合鈔箱 Aj中的數(shù)組 Sj：Sj1、Sj2…Sj,Xj中找出一個(gè)最接近但不大于殘值Cj的Sji，其中1≤i≤Xj，Xj為混合鈔箱Aj中剩余鈔票數(shù)，如果Sji不存在，轉(zhuǎn)步驟(5)繼續(xù)進(jìn)行配鈔，否則轉(zhuǎn)步驟(3)繼續(xù)進(jìn)行配鈔。

(3)計(jì)算殘值Cj+1=Cj-Sji。如果Cj+1=0，則配鈔結(jié)束，否則j=j+1繼續(xù)按照步驟(4)進(jìn)行。

(4)判斷 j≤m是否成立，是則轉(zhuǎn)步驟(2)繼續(xù)進(jìn)行配鈔，否則按照步驟(5)繼續(xù)進(jìn)行配鈔。

(5)對(duì)步驟(4)所得殘值Cj+1用單一面額鈔箱按照現(xiàn)有技術(shù)進(jìn)行配鈔，配鈔成功，流程結(jié)束，否則轉(zhuǎn)步驟(6)繼續(xù)配鈔。

(6)對(duì)Sji，計(jì)算i=i-1，如果 i≥1，則計(jì)算Cj+1=Cj+1+Sji-Sj(i-1)，繼續(xù)進(jìn)行步驟(5)配鈔；否則i＜1，繼續(xù)按照步驟(7)進(jìn)行配鈔。

(7)對(duì)于Cj+1，計(jì)算j=j-1，如果 j≥1，則計(jì)算Cj+1=Cj+1+Sji-Sj(i-1)，繼續(xù)進(jìn)行步驟(5)配鈔；否則混合鈔箱不參與配鈔，只用單一鈔箱按照現(xiàn)有技術(shù)進(jìn)行配鈔，配鈔成功，流程結(jié)束；否則配鈔失敗，流程結(jié)束。

3.2.2 單一面額鈔箱優(yōu)先法

單一面額鈔箱優(yōu)先法配鈔算法如下：

(1)當(dāng)配鈔總額Total不能被所有單一面額鈔箱的所有面額的最大公約數(shù)整除時(shí)，則按照步驟(2)繼續(xù)進(jìn)行配鈔；否則按照現(xiàn)有技術(shù)進(jìn)行配鈔，配鈔成功則流程結(jié)束，配鈔失敗則按照步驟(2)繼續(xù)進(jìn)行配鈔。此時(shí)只有混合面額的鈔箱A參與配鈔，配鈔才有可能成功。

(2)不妨設(shè)自助設(shè)別配備有m個(gè)混合面額鈔箱，假設(shè)Ai鈔箱有Xi張剩余鈔票，假設(shè)配鈔過(guò)程中混合鈔箱的出鈔數(shù)組為D，D1為第一張要出鈔的鈔票，Di為第i張要出鈔的鈔票。

則對(duì)于A1，A2……Am，按照上述混合面額鈔箱優(yōu)先法中的方法，得到Am的數(shù)組Sm：Sm1,Sm2…Sm,Xm。

將A1的數(shù)組S1各個(gè)元素：S11,S12…S1,X1，A2的數(shù)組S2各個(gè)元素：S21,S2…S2,X2，以及 Am的數(shù)組 Sm各個(gè)元素：Sm1,Sm2…Sm,Xm，按照從小到大的順序排列，構(gòu)成一個(gè)數(shù)組Sn，其中 n 為對(duì)任何1≤i≤j≤X1+X2+…+Xm的正整數(shù)i，j，均有Si＜Sj。令i=1，則繼續(xù)步驟(3)。

(3)計(jì)算殘值Ci=Total-Si，當(dāng)Ci不能被所有單一面額鈔箱的所有面額的最大公約數(shù)整除時(shí)，則按照步驟(4)繼續(xù)進(jìn)行配鈔；否則按照現(xiàn)有技術(shù)進(jìn)行配鈔，配鈔成功則流程結(jié)束，配鈔失敗則按照步驟(4)繼續(xù)進(jìn)行配鈔。

舉例略。

4 其他配鈔算法應(yīng)用

在實(shí)際應(yīng)用中，可以由單一面額鈔箱配鈔和混合面額鈔箱配鈔衍生出多種使用情形。

4.1 總金額非精確法的配鈔計(jì)算

單一面額鈔箱配鈔，在實(shí)際應(yīng)用中，有精確配鈔法和非精確配鈔之分，以下介紹總金額非精確配鈔法。

此時(shí)，找出一個(gè)盡可能小正數(shù)△m值，使得gcd(A1，A2…An)可以整除M-△m ，然后按照n=0，1，2…順序遞增，在條件△m+n·gcd(A1，A2…An)不大于允許誤差下，求解。直到找出一組合適的解或者△m+n·gcd(A1，A2…An)大于允許誤差為止。

4.2 限制面額張數(shù)需求的配鈔計(jì)算

單一面額鈔箱配鈔，在實(shí)際應(yīng)用中，還有限制面額需求張數(shù)與不限制面額需求張數(shù)之分。

不妨設(shè)自助設(shè)備各可用面額從小到大依次為A1，A2…An，各面額的可用鈔票數(shù)分別為 C1，C2…Cn。

設(shè)用戶輸入的出鈔金額為M，對(duì)各面額需求的張數(shù)分別為不少于B1，B2…Bn，設(shè)所求的各面額對(duì)應(yīng)的配鈔張數(shù)為X1，X2…Xn，最終的出鈔金額為M，設(shè)自助設(shè)備對(duì)一切0≤i≤n的整數(shù) i，均有 Bi≤Ci。將方程轉(zhuǎn)化為求，不妨設(shè) Yi=Xi-Bi，則方程轉(zhuǎn)化為

4.3 其他配鈔算法

(1)回收鈔票數(shù)期望最小的配鈔法：通過(guò)對(duì)統(tǒng)計(jì)ATM本加鈔周期各鈔箱的鈔票回收率，使得回收率最低的鈔箱盡可能地多出鈔的配鈔方法。該種方法使得回收箱盡可能空，解決了現(xiàn)金業(yè)務(wù)回收箱瓶頸問(wèn)題。

(2)限制各面額需求的優(yōu)化配鈔法：如果限制各面額需求時(shí)發(fā)生配鈔失敗，在進(jìn)行配鈔計(jì)算時(shí)，可采取盡可能滿足用戶面額需求的配鈔計(jì)算，從而可以向用戶提供出鈔建議，提高業(yè)務(wù)成功率和用戶滿意度。該方法可以細(xì)分為大面額需求張數(shù)優(yōu)先滿足法、小面額需求張數(shù)優(yōu)先滿足法、需求總張數(shù)差異最小法、各面額差異均等法等多種情況。

(3)混合面額鈔箱發(fā)生回收情況下的二次配鈔：在混合鈔箱出鈔時(shí)，若發(fā)生混合面額鈔箱中的某張鈔票出鈔被回收，則應(yīng)暫停出鈔；根據(jù)配鈔額度和已出鈔總額獲得出鈔余額；對(duì)所述出鈔余額繼續(xù)進(jìn)行配鈔，得到續(xù)鈔結(jié)果；根據(jù)所述續(xù)鈔結(jié)果繼續(xù)出鈔。

(4)多個(gè)混合鈔箱聯(lián)合配鈔法：可先計(jì)算出每一個(gè)混合鈔箱的前i張面額之和，構(gòu)成一個(gè)數(shù)組，j個(gè)鈔箱就會(huì)有j個(gè)數(shù)組。然后利用組合法，從j個(gè)數(shù)組的每一個(gè)數(shù)組每次僅取出一個(gè)元素，共有j個(gè)元素，j個(gè)元素之和形成的集合，就是能夠成功配鈔的總金額。如果要求配鈔的總金額不在上述集合中，則無(wú)法配鈔。

(5)混合鈔箱可分離張數(shù)的配鈔法：即一個(gè)或多個(gè)混合鈔箱聯(lián)合配鈔，采用出鈔時(shí)故意回收掉極少數(shù)幾張鈔票，剩余出鈔的鈔票滿足總金額的方法，該方法可以提高配鈔成功率。

5 結(jié)論

本文對(duì)金融自助終端的配鈔方法進(jìn)行了研究，建立了各種配鈔需求的數(shù)學(xué)模型并進(jìn)行了求解，解決了目前ATM技術(shù)領(lǐng)域配鈔算法時(shí)間復(fù)雜度過(guò)高和算法具有不確定性的弊端，實(shí)現(xiàn)了金融自助終端高效率的配鈔，本文的研究成果已應(yīng)用于國(guó)內(nèi)外自助設(shè)備10萬(wàn)臺(tái)級(jí)以上，產(chǎn)生了良好的經(jīng)濟(jì)效益。