找零的兩種問題

硬幣找零問題，有兩種。一種用貪心解決，一種用動態規劃解決。
問題1：假設我們有 v1，v2，……，vn（單位是元）這些幣值的硬幣，它們的張數分別是 c1、c2、…, cn。我們現在要用這些錢來找零 w元，最少要用多少張紙幣呢？

問題2：假設我們有幾種不同幣值的硬幣 v1，v2，……，vn（單位是元）。如果我們要支付 w 元，求最少需要多少個硬幣。比如，我們有 3 種不同的硬幣，1 元、3 元、5 元，我們要支付 9 元，最少需要 3 個硬幣（3 個 3 元的硬幣）。

問題1有一個限制條件是不同面額的硬幣的張數是有限制的，而問題2中沒有這個限制。

問題1解決用貪心。選擇小于w的，面值最大的硬幣，來付錢。

問題2解決用動態規劃。至于為什么不用貪心，我也不大明白。接下來重點描述問題2的解決方法。

回溯法解決問題2

回溯法1

因為多次用了回溯法，所以很自然想到，每次決定一種硬幣，使用一種數量，會產生什么狀態。
例如w=9，
在第0階段，我可以決定1元，使用0張，產生一種狀態：支付0元；1元，使用1張，產生一種狀態：支付1元；1元，使用2張，產生一種狀態：支付2元…
在第1階段，我可以決定3元，使用0張，基于上一步的狀態產生新的狀態：支付0、1、2…元；使用1張，基于上一步的狀態產生新的狀態：1+3、2+3…
當支付金額等于9的時候，比較最少使用了多少個硬幣。

public class CoinChange {//錢幣種類private int[] coins = new int[]{1,3,5};private int n = coins.length;//總金額private int total = 9;private int minCount = Integer.MAX_VALUE;private void f (int i,int coinCount, int sum){if(sum==total){minCount = Math.min(minCount,coinCount);return;}if(sum>total){return;}if(i==n){return;}int maxCount = (total - sum)/coins[i];System.out.println(maxCount);for(int j=0;j<=maxCount;j++){f(i+1,coinCount+j,sum+coins[i]*j);}}public int findCoinCount(){f(0,0,0);return minCount;}}

回溯法2

我們還可以換一種思路。我們按照支付金額分階段。
我們硬幣種類有1 元、3 元、5 元。設F(9)表示想要支付9元最少需要幾個硬幣。F(9)可以從F(9-1)、F(9-3)、F(9-5)三個狀態過來，分別在這三個狀態+1，選擇最低值就是F(9)最少需要支付多少個硬幣。

定義狀態轉移公式：
$F(S)=mi{n}_{i=0,1,2...n?1}(F(S?c_i))+1$ ,subject to $S?c_i>=0$
$F(0)=0$
$F(S)=?1$,when $n=0$

上一種回溯中是以每次選擇一種硬幣作為階段。這次是每次支付夠1元，2元，3元…n元，為階段。

public class CoinChangeV3 {//錢幣種類private int[] coins = new int[]{1,3,5};private int n = coins.length;//總金額private int total = 9;private int f (int total){if(n==0) return -1;if(total == 0) return 0;int minCount = Integer.MAX_VALUE;for(int i=0;i<n;i++){if(coins[i]<=total){int count = f(total-coins[i]);minCount = Math.min(count,minCount);}}return minCount==Integer.MAX_VALUE?-1:minCount+1;}public int findCoinCount(){return f(total);} }

備忘錄模式

基于上面的回溯畫出這樣的遞歸樹。樹中的每一個節點是一種狀態，用f(total)表示。total表示當前方法要支付多少元。（這感覺不像是以前那種狀態）我們看到(3). (5)都重復計算了很多次。可以采用備忘錄模式，減少計算次數。

public class CoinChangeV3 {//錢幣種類private int[] coins = new int[]{1,3,5};private int n = coins.length;//總金額private int total = 9;private int f (int total,int[] memory){if(n==0) return -1;if(total == 0) return 0;if(memory[total] !=0) return memory[total];int minCount = Integer.MAX_VALUE;for(int i=0;i<n;i++){if(coins[i]<=total){int count = f(total-coins[i],memory);minCount = Math.min(count,minCount);}}memory[total] = minCount==Integer.MAX_VALUE?-1:minCount+1;return memory[total];}public int findCoinCount(){int[] memory = new int[total+1];return f(total,memory);}}

動態規劃

根據動態轉移方程計算。

public int findCoinCountDp(){int max = total+1;int[] dp = new int[total+1];Arrays.fill(dp,max);dp[0] = 0;for(int i=1;i<=total;i++){for(int j=0;i<coins.length;j++){if(coins[j]<=i){dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);}}}return dp[total]==max?-1:dp[total];}

放在最后的一點體會。將問題抽象為多階段決策問題，要分清楚是按照什么分階段。一般來講是按照目標指標分階段。例如支付9元最少需要多少個硬幣，分階段為支付8元最少需要多少個硬幣，支付7元最少需要多少個硬幣…。例如從(0,0)走到(n-1,n-1)最少需要多少步，目標是(n-1,n-1)，前一步可以是(n-1,n-2)或者(n-2,n-1)，知道他們的最少步數+1，就是目標值，所以可以按照到達的坐標分階段。
按照某個指標做分階段，回溯法枚舉的時候不一定與此相關。回溯法枚舉的時候，枚舉的是選項。例如不同面值的硬幣，不同的前進方向。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的动态规划——硬币找零思路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。