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

問題描述

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

分析問題

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

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

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

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

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

……

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

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

舉例：假設(shè)你要求63的最小硬幣數(shù)，那么你需要這樣計(jì)算：63-1=62、63-5=58、63-10=53。假設(shè)62、58、53對(duì)應(yīng)的最小硬幣數(shù)已經(jīng)被你記錄在了備忘錄數(shù)組。這時(shí)候你只需要找出62、58、53中誰對(duì)應(yīng)的最小硬幣數(shù)最小，然后加1，就是63對(duì)應(yīng)的最小硬幣數(shù)。因?yàn)?3比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]對(duì)應(yīng)0，money[1]對(duì)應(yīng)1，money[2]對(duì)應(yīng)2……

接下來，將我們上邊的解題思路抽象成函數(shù)，函數(shù)中無非就是：循環(huán)，判斷，賦值……如何利用這些邏輯語句，將我們的思路描述出來，這是最難的，因?yàn)橐龅降嗡宦闆r都要考慮周全，一步錯(cuò)結(jié)果就錯(cuò)，這需要長久鍛煉抽象邏輯思維。我比較習(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ù)組，一一對(duì)應(yīng) int[] memo = new int[money + 1]; //0元對(duì)應(yīng)的最小硬幣數(shù)是0 memo[0] = 0; System.out.println( '金額t' + '對(duì)應(yīng)的最小硬幣數(shù)' ); //遍歷備忘錄數(shù)組，為每個(gè)金額記錄他的最小硬幣數(shù)，我們從1元開始 for( int currentMoney = 1 ; currentMoney <= money ; currentMoney++ ) { //默認(rèn)最小硬幣數(shù)就是當(dāng)前金額的本身 //舉例：63元最多就是63個(gè)1元的硬幣唄 int minCoins = currentMoney; //遍歷硬幣面額數(shù)組，找到前邊所能找到的最小硬幣數(shù)加1 for( int coinKind = 0 ; coinKind < coins.length ; coinKind++ ) { //只有當(dāng)前金額大于等于某個(gè)硬幣面額的時(shí)候才可以用這種方法 //舉例：5-1=4,5-5=0,5-10=-5，我們沒有-5元好吧…… if( currentMoney >= coins[coinKind] ) { //我們在備忘錄中查找之前的金額對(duì)應(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)前金額對(duì)應(yīng)的最小硬幣數(shù)，我們將它記錄在備忘錄中 memo[currentMoney] = minCoins; System.out.println( currentMoney + 't' + memo[currentMoney] ); }}

運(yùn)行結(jié)果

金額對(duì)應(yīng)的最小硬幣數(shù)1122334451627384951011121231341451521631741851962022132242352462532642752862973033143253363473543653763873984044154264374484554664774884995055165275385495565675785895910606617628639

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。