自助設(shè)備配鈔算法初探摘要目前自助設(shè)備配鈔算法技術(shù)，一種面額容易處理，兩種或兩種面額以上，一般采用窮舉法，窮舉法肯定不是最優(yōu)算法，又由于各面額出鈔張數(shù)的各類限制，如各面額可用鈔票數(shù)限制、系統(tǒng)預(yù)設(shè)的出鈔原則限制，還有可能是用戶對(duì)各面額出鈔張數(shù)的限制，使得窮舉法的開(kāi)銷(xiāo)比較大。本文提供一種直接求解多元一次正整系數(shù)方程的通解方法，利用各面額出鈔張數(shù)的各類限制，直接對(duì)通解中的自由因子進(jìn)行范圍限制，最終成功得到可行的配鈔方案。本配鈔方法直觀、高效、快速、嚴(yán)謹(jǐn)，不必要使用窮舉法，就很快找出所有配鈔方案，具有配鈔時(shí)間少，配鈔效率高等優(yōu)點(diǎn)。1前百金融自助設(shè)備配鈔是指對(duì)自動(dòng)柜員機(jī)中各個(gè)鈔箱中不同面額的鈔票數(shù)量進(jìn)行統(tǒng)籌管理。一般地，金融自助設(shè)備裝有至少一個(gè)鈔箱，至少有一種面額，每一個(gè)鈔箱裝有一定數(shù)量的相同面額的鈔票。在出鈔時(shí)，需要對(duì)用戶輸入金額按照各種面額進(jìn)行配鈔，在優(yōu)先滿足用戶需求的同時(shí)，也要兼顧加鈔維護(hù)，因此，每次出鈔進(jìn)行配鈔，需要根據(jù)用戶輸入金額和鈔箱可用鈔票生育情況，進(jìn)行綜合管理。目前主要有五種配鈔原則：各鈔箱均空法：各個(gè)面額的鈔票以近乎相同的概率被清空。各鈔箱平均法：按照各個(gè)面額張數(shù)近乎相等的配鈔方案進(jìn)行出鈔。大面額優(yōu)先法：優(yōu)先出面額大的，按照該種方案出鈔，但總張數(shù)不一定最小。小面額優(yōu)先法：按照總張數(shù)最多的配鈔方案進(jìn)行出鈔。總張數(shù)最小法：按照各面額出鈔總張數(shù)最小的配鈔方案進(jìn)行出鈔。2配鈔建模本文提供了一種金融自助設(shè)備配鈔方法，利用直接求解一元多次整系數(shù)方程的整數(shù)解的通解辦法，得出一元多次方程的整數(shù)解的通解辦法，然后根據(jù)各面額配鈔數(shù)額必須大于零，且小于自助設(shè)備該種面額的剩余可用鈔票數(shù)，且不小于用戶要求的各面額需求張數(shù)，求解出通解公式中自由因子的限定范圍，從而很快得出了所有的配鈔方案數(shù)。最后依據(jù)自助服務(wù)系統(tǒng)的配鈔原則（均空法、平均法、最小張數(shù)法、最大面額優(yōu)先法、最小面額優(yōu)先法），得出一種最優(yōu)化的配鈔方案。根據(jù)本文提供的一種金融自助設(shè)備配鈔方法，不妨假設(shè)自助設(shè)備上有n種面額，各個(gè)面A、AA A、AA額的面額值從小到大依次為A1、A2n，自助設(shè)備上各個(gè)面額A1、A2n對(duì)應(yīng)的可用的張數(shù)Si、S2…Sn，用戶要求的各面額最低需求張數(shù)B、B...B，現(xiàn)需要對(duì)配鈔金額為M進(jìn)1 2n

行配鈔，設(shè)各個(gè)面額的配鈔張數(shù)為X1、X2…Xn,則有關(guān)系式：A1X1+A2X2+…+AnX廠M即1LaX=Mi=1ii，其中B<X<S,B<X<S...B<X<S。1 1 1 2 2 2nnn3配鈔求解本文所述的金融自動(dòng)設(shè)備配鈔方法，包括如下步驟：S2：判斷配鈔金額是否不大于所述金融自助設(shè)備中鈔箱剩余金額總數(shù)，是則轉(zhuǎn)步驟S3；否則配鈔失敗，結(jié)束。S3：求出各面額值的最大公約數(shù)，判斷各面額值的最大公約數(shù)是否可以整除配鈔金額，是則轉(zhuǎn)步驟S4；否則配鈔失敗，結(jié)束?！鎑(AAA) ^^A^X^=MS4：判斷兩面額值的最大公約數(shù)gCd(A1，4C是否大于1，是則將i=1 兩?！赋鯝AA) “ EaXrm邊同除以g(A1，A2-AnL得到型如n元一次整系數(shù)不定方程i=1 ，其中g(shù)Cd(a1,a2,..."=L且M二mgCd(A1，4…4)；否則」‘保持原樣。￡aX=mS5：n元一次整系數(shù)不定方程i=1'' 中，如果"J"2'…'"n中存在兩個(gè)互質(zhì)的系數(shù)1，是則轉(zhuǎn)S6,否則按照下述方法轉(zhuǎn)化為具有兩個(gè)互質(zhì)系數(shù)的等價(jià)的n元一次方程：由于aja2"的絕對(duì)值都大于1，找出絕對(duì)值最小的一個(gè)系數(shù)，且不妨設(shè)a1>0，則其他系數(shù)可以表示為："?=kJ+r"<r<a1(i=2'3,…'n).此時(shí)原方程可轉(zhuǎn)化為:，rn中有某兩個(gè)互a(x+kxd—Fkx)+rx+rxd—Frx=M若a，rn中有某兩個(gè)互6x+10y+15z=1170質(zhì)，則轉(zhuǎn)步驟6x+10y+15z=1170可以轉(zhuǎn)化為6(x+y+2z)+4y+3z=11706UF4yF3z-1170，其中y的系數(shù)4與z的系數(shù)3互質(zhì)了。EbY-mS6：多元一次方程等價(jià)轉(zhuǎn)換成型如,-1ii 的至少具有兩個(gè)互質(zhì)的系數(shù)的多元一次

士的丁/、八（b，b）=1引〃bY+bY=m-（bY+???+bY）b,bY+bY=1M萬(wàn)程，不妨設(shè)12,，那么11 22 33 nn。若11 22的一rY<01個(gè)特解為1%2，其中b1Y1+b2Y2=1特解求解方法見(jiàn)前述S4兩種面額配鈔法?！阞Yrm （bb）=1S7：n元一次不定方程,=1 （其中（b1,b2）1）的通解公式為:Y=Y[m-(bY+???+bY)]+btY2=Y02[m-(bY3+-+bY)]-bt其中t，ZV,…其中t，ZV,…，YnEZ。于是就可以求出的解。6X1+10X2+的解。6X1+10X2+15X3=1170可以轉(zhuǎn)化為6(X1+X2+2XJ+4X2+3X3=11706u44X43X=117023至此，已經(jīng)將6X1+10X2+15X3=1170轉(zhuǎn)換為具有兩個(gè)互質(zhì)系數(shù)的等價(jià)的其中y1=U,X2其中y2的系數(shù)4與y3的系數(shù)3互質(zhì)了。因此只要求解出6y144y243y3=1170的正整數(shù)解，就相應(yīng)的可以求出1的正整數(shù)解了。y=-543t(teZ)由于4y243y3=1的通解為:y=7-41 4由于4y243y3=1的通解為:3 ，則J2 々 的通解為：y=-5(1170-6u)43t2 (t、y=7(1170-6u)-413又因?yàn)閄1=u-X2-2X3=u-9(1170-6u)-11t=55u-11t-10530于是6X1于是6X1410X2415X3=1170的通解為'X=55u—11/-10530<X=-5(1170-6u)+3t,其中(入ueZ)2X=7(1170-6u)-4133由此可見(jiàn)，n元一次不定方程在有解前提下，如存在兩個(gè)系數(shù)的最大公約數(shù)是1,則它的通解中含有n-1個(gè)參變量，其中的n-2個(gè)參變量都可以取原來(lái)的變?cè)8：根據(jù)B］<X1<SjB2VX2VS2...B4X4Sn(B,B…Bn為用戶對(duì)各面額的最低需求張數(shù)，S1,S2…Sn為各面額的剩余可用鈔票數(shù))，由此可以求出整數(shù)t的取值范圍。XXXS9：根據(jù)配鈔原則，進(jìn)一步限制X1,X2Xn的值，根據(jù)配鈔原則的不同，可分為以下幾種情況，在［112］范圍內(nèi)確定t的取值：m2|x-1ExI)S51)各鈔箱平均法，此時(shí)""X2"…"Xn，有 尸1 j巴=1'取最小值；S52)各鈔箱均空法，此時(shí)X1-S1"X2-S2"…"Xn-Sn，有瓜=E(I(X-S)-1NX-S)I)產(chǎn)1 jjni=1ii取最小值；Ex min(Ex)S53)最小總張數(shù)法，i=1i盡可能小，即求 i=1i；S54)最小面額優(yōu)先法，如果A是所有面額最小者，Xi盡可能大；S55)最大面額優(yōu)先法，如果A是所有面額最大者，Xi盡可能大。4配鈔舉例假設(shè)自助設(shè)備配備有四種面額100、50、20、15,即A=10'250 人昔擊4剩余可用鈔票分別為：S1=15,S2=10,S3=18,S4=20。如果用戶輸入金額為1565，由于100、50100、50、20、15的最大公約數(shù)為5，1565%gcd(100,50,20,5)=0根據(jù)100X1100X1+50X2+20X3+15X4=1565兩邊同除5 ，得到20X+10X+4X+20X+10X+4X+3X=313由于X3、X4互質(zhì)，所以方程變?yōu)槎淮畏匠?[X=—5+3t4X+3X=313—20X-10X342,由于的通解為：i3X=7-4t42的通解為:4X+3X=313-20X-102的通解為:34X=-5(313-20X-10X)+3tX=7(313-20X-10X)-410<X<S,0<X<S,0<0<X<S,0<X<S,0<X<S,0<X<S11223344=15,S=10,S=18,S=20得到0<X<15,?X<10,018<,X0 < 204可得到-87<313-20X-10X<313確定t的取值范圍為-145<t<527X1X1）如果是平均出鈔法，有X1Ax=E(|X-1￡x|)xXXXXX jni2 3 4根據(jù) j=1 i=1 有'J'J。X?+X4|+1X'J。X?+X4|+1X最小，即-5(313-20X-10X)+最小，即-5(313-20X-10X)+3tx7(313-20X-10X)-41xXxXt=108,X=8,X=9,X=9,X=9,Ax=1.5為所求配鈔方案（8,9,9,9）。2）如果是均空法有X1-S1xX2-S2xX3-S3Ax=￡(|(X-S)-1￡(X-S)|)jjniij=1 i=1t=159,X=9,X=4,X=12,X4=15,Ax=L5為所求配鈔方案，各面額原有（15,10，18，2018，20），出鈔后剩余為（6，6，6，5）。3）如果是張數(shù)最小法，有（X1+X2+X3+X4）盡可能小，即(626-39X-19X-1)盡可能小，min(626盡可能小，min(626-39X-19X-1)=17，得到最小張數(shù)為17張，X= X= 10為所求11鈔方案（15，1，0，1）。XX4）如果是最大面額優(yōu)先法，有X1盡可能大，其次X2盡可能大，再次X3盡可能大，得到t=5,得到t=5,X=15,X=1,X=0,X=1為所求配鈔方案（15，1，01）。再次再次X2盡可能大，XX5）如果是最小面額優(yōu)先法，有X4盡可能大，其次X3盡可能大，得到‘二193,X1=5,X2=10，X3=14,X4=19為所求配鈔方案(5,10,14,19),各面額原有(15,10,18,20),出鈔后各面額剩余(10,0,4,1)。5結(jié)論