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

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

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

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

問題描述

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

分析問題

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

1元對應(yīng)的最小硬幣數(shù)是1

2元對應(yīng)的最小硬幣數(shù)是2

3元對應(yīng)的最小硬幣數(shù)是3

4元對應(yīng)的最小硬幣數(shù)是4

……

63元對應(yīng)的最小硬幣數(shù)是XXX

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

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

按照這種備忘錄思想，我們進(jìn)行編程。首先將我們要處理的數(shù)據(jù)轉(zhuǎn)換成數(shù)組和必要參數(shù)。

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

說明：money數(shù)組就是備忘錄數(shù)組，例如：money[0]對應(yīng)0，money[1]對應(yīng)1，money[2]對應(yīng)2……

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

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

運行結(jié)果

金額        對應(yīng)的最小硬幣數(shù)
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