兌換零錢(qián)問(wèn)題的動(dòng)態(tài)規(guī)劃算法研究

摘要：兌換零錢(qián)問(wèn)題是一個(gè)求解組合優(yōu)化的問(wèn)題。首先對(duì)兌換零錢(qián)問(wèn)題進(jìn)行了分析，證明了該問(wèn)題滿足動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，并給出了其動(dòng)態(tài)規(guī)劃解法；然后對(duì)本算法進(jìn)行了時(shí)間復(fù)雜性和空間復(fù)雜性分析，得到時(shí)間復(fù)雜性由通常的動(dòng)態(tài)規(guī)劃算法的O(Mn²)提高到本算法的O(n³)，空間復(fù)雜性由通常的動(dòng)態(tài)規(guī)劃算法的O(Mn)提高到本算法的O(n²)，因此效率有了較大提高。最后通過(guò)實(shí)驗(yàn)對(duì)算法進(jìn)行驗(yàn)證，證明了算法的高效性。該算法可以廣泛應(yīng)用于自動(dòng)售貨機(jī)。

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃； 兌換零錢(qián)問(wèn)題； 算法復(fù)雜性

中圖分類號(hào)：TP311．11文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)12-0088-03

動(dòng)態(tài)規(guī)劃是求解決策過(guò)程的有效最優(yōu)數(shù)學(xué)方法之一^[1~3]。它為具有最優(yōu)子結(jié)構(gòu)性質(zhì)的實(shí)際問(wèn)題提供了一種重要的解決問(wèn)題的途徑^[4，5]。該策略最早由Bellman提出^[4，6]，它利用最優(yōu)性原理和所獲得的遞推關(guān)系去解最優(yōu)決策序列，從而使問(wèn)題的計(jì)算量急劇下降。利用動(dòng)態(tài)規(guī)劃策略求解的問(wèn)題通常可能會(huì)有許多可行解，每個(gè)解均對(duì)應(yīng)一個(gè)值，動(dòng)態(tài)規(guī)劃求解過(guò)程希望獲得具有最優(yōu)值的那個(gè)解^[7]。多年來(lái)，人們?cè)谶@一領(lǐng)域進(jìn)行了積極的研究，給出了很多具有重疊子問(wèn)題特定問(wèn)題的動(dòng)態(tài)規(guī)劃解法。詳細(xì)情況可參見(jiàn)文獻(xiàn)[8，9]。

兌換零錢(qián)問(wèn)題有其廣泛的應(yīng)用前景，如應(yīng)用到自動(dòng)售貨機(jī)上進(jìn)行零錢(qián)兌換。被稱為“永不下班的超級(jí)營(yíng)業(yè)員”的自動(dòng)售貨機(jī)在中國(guó)特別是發(fā)達(dá)國(guó)家越來(lái)越普及，但目前自動(dòng)售貨機(jī)出售商品時(shí)，機(jī)器只能接收硬幣和小額紙幣，影響到消費(fèi)者的選擇^[10]。如何解決該問(wèn)題，其中關(guān)鍵的技術(shù)包括對(duì)大額紙幣的零錢(qián)兌換問(wèn)題。由于運(yùn)行在自動(dòng)售貨機(jī)上，設(shè)計(jì)一個(gè)高效的兌換零錢(qián)算法對(duì)于本問(wèn)題相當(dāng)重要。本文首先分析了用貪心算法解決該問(wèn)題。由于貪心算法固有的缺點(diǎn)決定了其并不總能解決最優(yōu)問(wèn)題，還需要進(jìn)行證明^[7]其算法的最優(yōu)性。比如說(shuō)世界上通行的貨幣體制為十進(jìn)制，這種貨幣體制的零錢(qián)兌換問(wèn)題用貪心算法兌換可以證明是最優(yōu)的。但有少數(shù)的幣制不是十進(jìn)制的就未必能用貪心算法兌換，如對(duì)于以前的英國(guó)貨幣單位是1英鎊等于20先令，1先令等于12便士；同樣，以前法國(guó)的幣制也存在這樣的問(wèn)題。因此本文對(duì)該問(wèn)題用動(dòng)態(tài)規(guī)劃算法加以解決，以避免非十進(jìn)制換算的幣制體系不能用貪心算法解決。其間證明了兌換零錢(qián)問(wèn)題可以進(jìn)行動(dòng)態(tài)規(guī)劃，給出了該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)的證明以及該問(wèn)題的遞歸結(jié)構(gòu)（重疊子問(wèn)題）；同時(shí)用C++實(shí)現(xiàn)了其動(dòng)態(tài)規(guī)劃算法。最后對(duì)該算法的復(fù)雜度進(jìn)行了分析。

參考文獻(xiàn)：

[1]費(fèi)蓉， 崔杜武.中國(guó)郵遞員問(wèn)題的動(dòng)態(tài)規(guī)劃算法研究[J]. 計(jì)算機(jī)研究與發(fā)展，2005，42(2):294-299.

[2]文貢堅(jiān)， 周秀芝. 基于視差點(diǎn)的大遮擋檢測(cè)和立體匹配方法[J].軟件學(xué)報(bào)，2005，16 (5):708-717.

[3]楊娟， 邱玉輝，李建國(guó)，等. 一種應(yīng)用部件可動(dòng)態(tài)規(guī)劃的MA模型[J]. 計(jì)算機(jī)研究與發(fā)展， 2005，42(5):830-834.

[4]DREYFUS S. Richard Bellman on the birth of dynamic programming［EB/OL］.(2002).http://www.eng.tau.ac.il/~ami/cd/or50/1526-5463-2002-50-01-0048.pdf.

[5]祝遠(yuǎn)新， 徐光祐，俞志和. 基于表觀的動(dòng)態(tài)孤立手勢(shì)識(shí)別[J]. 軟件學(xué)報(bào)， 2000， 11(1): 54-61.

[6]COOPER R. Dynamic programming:an overview［EB/OL］ .（2000-02）.http://econ.bu.edu/faculty /cooper/dynprog/introlect.pdf.

[7]ALSUWAIYEL M H. Algorithms design techniques and analysis［M］.Beijing: Publishing House of Electronics Industry， 2003:203-204.

[8]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析［M］.北京：電子工業(yè)出版社， 2001: 43-44.

[9]NIST.Dynamic programming ［EB/OL］.(2005).http://www.nist.gov/dads/HTML/dynamicprog.html.

[10]葉國(guó)際，呂惠敏.外商看好我國(guó)的自動(dòng)售貨機(jī)市場(chǎng)［EB/OL］.(2002-05-24). http://www.clima.org.cn/dzku/tx0703.htm.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”