硬幣找零動(dòng)態(tài)規(guī)劃算法

硬幣找零動(dòng)態(tài)規(guī)劃目錄2023/2/11234問(wèn)題描述問(wèn)題分析問(wèn)題解決實(shí)驗(yàn)總結(jié)問(wèn)題描述2023/2/1硬幣找零問(wèn)題描述：現(xiàn)存在一堆面值為V1、V2、V3…個(gè)單位的硬幣，問(wèn)最少需要多少個(gè)硬幣才能找出總值為T(mén)個(gè)單位的零錢(qián)？假設(shè)這一堆面值分別為1、2、5、21、25元，需要找出總值T為63元的零錢(qián)。很明顯，只要拿出3個(gè)21元的硬幣就湊夠了63元了。對(duì)于這個(gè)問(wèn)題，不妨采用貪心法很明顯，只要拿出25，25，5，5，2，1的硬幣湊夠了63元了。顯然使用貪心法竟需要拿出6個(gè)硬幣。我們發(fā)現(xiàn)貪心算法不能求出最少的硬幣數(shù)。因此我們需要再尋找另一種算法來(lái)求出最少的硬幣數(shù)。問(wèn)題分析2023/2/1對(duì)于此題，可以先舉個(gè)簡(jiǎn)單的例子：若有1，5，7，10這四種貨幣，則易知

1=12=1+13=1+1+14=1+1+1+15=0+56=5+1……11=10+1問(wèn)題分析2023/2/1D[12]min=

Min(d[12-1],d[12-5],d[12-7],d[12-10])+1=2面值iD[i]最少貨幣數(shù)那么對(duì)于任意的面值i來(lái)說(shuō)，D[i]=min(D[i–a])+1(a∈{貨幣面值}且d[i–a]≠0){d[i]=0代表i無(wú)法用給定的貨幣表示}問(wèn)題分析2023/2/1

動(dòng)態(tài)規(guī)劃的基本思想是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，并將這些子問(wèn)題的解保存起來(lái)，如果以后在求解較大子問(wèn)題的時(shí)候需要用到這些子問(wèn)題的解（即原問(wèn)題的解包含其子問(wèn)題的解），就可以直接取出這些已經(jīng)計(jì)算過(guò)的解而免去重復(fù)運(yùn)算。保存子問(wèn)題的解可以使用填表方式，例如保存在數(shù)組中。問(wèn)題解決2023/2/1

基于上述動(dòng)態(tài)規(guī)劃的思想，我們可以從1元開(kāi)始計(jì)算出最少需要幾個(gè)硬幣，然后再求2元、3元…每一次求得的結(jié)果都保存在一個(gè)數(shù)組中，以后需要用到時(shí)則直接取出即可。那么我們什么時(shí)候需要這些子問(wèn)題的解呢？如何體現(xiàn)出原問(wèn)題的解包含其子問(wèn)題的解呢？

其實(shí)，在我們從1元開(kāi)始依次找零時(shí)，可以嘗試一下當(dāng)前要找零的面值（這里指1元）是否能夠被分解成另一個(gè)已求解的面值的找零需要的硬幣個(gè)數(shù)再加上這一堆硬幣中的某個(gè)面值之和，如果這樣分解之后最終的硬幣數(shù)是最少的，那么問(wèn)題就得到答案了。問(wèn)題解決2023/2/1此處添加公司信息面值iD[i]最少貨幣數(shù)D[63]min=

Min(d[63-1],d[63-2],d[63-5],d[63-21],d[63-25])+1=3問(wèn)題解決2023/2/1：結(jié)果實(shí)驗(yàn)總結(jié)2023/2/1

在解決問(wèn)題的過(guò)程中參考了書(shū)本里的內(nèi)容，通過(guò)本題我對(duì)算法分析設(shè)計(jì)又有了進(jìn)一步的了解，對(duì)動(dòng)態(tài)規(guī)劃算法有更多的認(rèn)識(shí)。動(dòng)態(tài)規(guī)劃的基本思想是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，并將這些子問(wèn)題的解保存起來(lái)，