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};//硬币面额数组
intadm=63;//要求的金额
int[]money=newint[63+1];//金额数组，也就是备忘录数组
说明：money数组就是备忘录数组，例如：money[0]对应0，money[1]对应1，money[2]对应2……
接下来，将我们上边的解题思路抽象成函数，函数中无非就是：循环，判断，赋值……如何利用这些逻辑语句，将我们的思路描述出来，这是最难的，因为要做到滴水不漏，情况都要考虑周全，一步错结果就错，这需要长久锻炼抽象逻辑思维。我比较习惯的方式是边看代码，边关联结题思路，然后模仿，代码中有注释，大家边看边分析吧：
publicstaticvoidmain(String[]args){
int[]coins={1,5,10};
intmoney=63;
changeMoney(coins,money);
}
/**
*硬币找零算法,备忘录方法
*@paramcoins硬币面额数组
*@parammoney目标金额
*/
publicstaticvoidchangeMoney(int[]coins,intmoney){
//备忘录数组，一一对应
int[]memo=newint[money+1];
//0元对应的最小硬币数是0
memo[0]=0;
System.out.println("金额\t"+"对应的最小硬币数");
//遍历备忘录数组，为每个金额记录他的最小硬币数，我们从1元开始
for(intcurrentMoney=1;currentMoney<=money;currentMoney++){
//默认最小硬币数就是当前金额的本身
//举例：63元最多就是63个1元的硬币呗
intminCoins=currentMoney;
//遍历硬币面额数组，找到前边所能找到的最小硬币数加1
for(intcoinKind=0;coinKind=coins[coinKind]){
//我们在备忘录中查找之前的金额对应的最小硬币数
//如果能查到就在它的基础上加1
inttempCoins=memo[currentMoney-coins[coinKind]]+1;
//找到几种情况中最小的硬币数
//举例：63元tempConis
//可以是memo[63-1]+1、memo[63-5]+1、memo[63-10]+1
//我们要找到最小的
if(tempCoins
运行结果
金额 对应的最小硬币数
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算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。