java動態(tài)規(guī)劃算法——硬幣找零問題實例分析

更新時間：2020年05月26日 09:59:47 作者：Z_DZ

這篇文章主要介紹了java動態(tài)規(guī)劃算法——硬幣找零問題,結合實例形式分析了java動態(tài)規(guī)劃算法——硬幣找零問題相關原理、實現方法與操作注意事項,需要的朋友可以參考下

本文實例講述了java動態(tài)規(guī)劃算法——硬幣找零問題。分享給大家供大家參考，具體如下：

問題描述

現在有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，這就是最優(yōu)解！

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

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

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

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

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