用實例解析java動態規劃算法中硬幣找零問題

小編這次要給大家分享的是用實例解析java動態規劃算法中硬幣找零問題，文章內容豐富，感興趣的小伙伴可以來了解一下，希望大家閱讀完這篇文章之后能夠有所收獲。

問題描述

現在有3種硬幣分別為：1元，5元，10元，現在給你63元，讓你全部換成硬幣，求出最小硬幣數量，也就是說，怎么用最少的硬幣數湊成63元。

分析問題

解決這個問題，我們可以將這個大問題分成若干個小問題，自下而上解決問題。

1元對應的最小硬幣數是1

2元對應的最小硬幣數是2

3元對應的最小硬幣數是3

4元對應的最小硬幣數是4

……

63元對應的最小硬幣數是XXX

假設我們將前邊計算出的金額對應的最小硬幣數像備忘錄一樣記錄下來，那么后邊金額對應的最小硬幣數的就好說了，為什么？

舉例：假設你要求63的最小硬幣數，那么你需要這樣計算：63-1=62、63-5=58、63-10=53。假設62、58、53對應的最小硬幣數已經被你記錄在了備忘錄數組。這時候你只需要找出62、58、53中誰對應的最小硬幣數最小，然后加1，就是63對應的最小硬幣數。因為63比62、58、53都大，最好的情況無非就是在62、58、53中找出最小的一種情況加1，這就是最優解！

按照這種備忘錄思想，我們進行編程。首先將我們要處理的數據轉換成數組和必要參數。

int[] coins = { 1 , 5 , 10 }; //硬幣面額數組
int adm = 63; //要求的金額
int[] money = new int[63+1]; //金額數組，也就是備忘錄數組

說明：money數組就是備忘錄數組，例如：money[0]對應0，money[1]對應1，money[2]對應2……

接下來，將我們上邊的解題思路抽象成函數，函數中無非就是：循環，判斷，賦值……如何利用這些邏輯語句，將我們的思路描述出來，這是最難的，因為要做到滴水不漏，情況都要考慮周全，一步錯結果就錯，這需要長久鍛煉抽象邏輯思維。我比較習慣的方式是邊看代碼，邊關聯結題思路，然后模仿，代碼中有注釋，大家邊看邊分析吧：

public static void main(String[] args) {
 
 int[] coins = {1,5,10};
 int money = 63;
 
 changeMoney(coins,money);
}
 
/**
 * 硬幣找零算法,備忘錄方法
 * @param coins 硬幣面額數組 
 * @param money 目標金額
 */
public static void changeMoney( int[] coins , int money ) {
 //備忘錄數組，一一對應
 int[] memo = new int[money + 1];
 //0元對應的最小硬幣數是0
 memo[0] = 0;
 
 System.out.println( "金額\t" + "對應的最小硬幣數" );
 //遍歷備忘錄數組，為每個金額記錄他的最小硬幣數，我們從1元開始
 for( int currentMoney = 1 ; currentMoney <= money ; currentMoney++ ) {
 //默認最小硬幣數就是當前金額的本身
 //舉例：63元最多就是63個1元的硬幣唄
 int minCoins = currentMoney;
 //遍歷硬幣面額數組，找到前邊所能找到的最小硬幣數加1
 for( int coinKind = 0 ; coinKind < coins.length ; coinKind++ ) {
 //只有當前金額大于等于某個硬幣面額的時候才可以用這種方法
      //舉例：5-1=4,5-5=0,5-10=-5，我們沒有-5元好吧……
 if( currentMoney >= coins[coinKind] ) {
 //我們在備忘錄中查找之前的金額對應的最小硬幣數
 //如果能查到就在它的基礎上加1
 int tempCoins = memo[currentMoney - coins[coinKind]] + 1;
 //找到幾種情況中最小的硬幣數
 //舉例：63元 tempConis 
 //可以是memo[63-1]+1、memo[63-5]+1、memo[63-10]+1
 //我們要找到最小的
 if( tempCoins < minCoins ) {
  minCoins = tempCoins;
 }
 }
 }
 //找到當前金額對應的最小硬幣數，我們將它記錄在備忘錄中
 memo[currentMoney] = minCoins;
 
 System.out.println( currentMoney + "\t" + memo[currentMoney] );
 }
}

運行結果

金額        對應的最小硬幣數
1        1
2        2
3        3
4        4
5        1
6        2
7        3
8        4
9        5
10        1
11        2
12        3
13        4
14        5
15        2
16        3
17        4
18        5
19        6
20        2
21        3
22        4
23        5
24        6
25        3
26        4
27        5
28        6
29        7
30        3
31        4
32        5
33        6
34        7
35        4
36        5
37        6
38        7
39        8
40        4
41        5
42        6
43        7
44        8
45        5
46        6
47        7
48        8
49        9
50        5
51        6
52        7
53        8
54        9
55        6
56        7
57        8
58        9
59        10
60        6
61        7
62        8
63        9

看完這篇關于用實例解析java動態規劃算法中硬幣找零問題的文章，如果覺得文章內容寫得不錯的話，可以把它分享出去給更多人看到。