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

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

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

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

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

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

其實，在我們從1元開始依次找零時，可以嘗試一下當前要找零的面值（這里指1元）是否能夠被分解成另一個已求解的面值的找零需要的硬幣個數(shù)再加上這一堆硬幣中的某個面值之和，如果這樣分解之后最終的硬幣數(shù)是最少的，那么問題就得到答案了。問題解決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問題解決2023/2/1：結(jié)果實驗總結(jié)2023/2/1

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