java动态规划算法——硬币找零问题实例分析
27 浏览量
2020-08-19
03:46:50
上传
评论
收藏 62KB PDF 举报
java动态规划算法动态规划算法——硬币找零问题实例分析硬币找零问题实例分析
主要介绍了java动态规划算法——硬币找零问题,结合实例形式分析了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( "金额 " + "对应的最小硬币数" );
//遍历备忘录数组，为每个金额记录他的最小硬币数，我们从1元开始
for( int currentMoney = 1 ; currentMoney <= money ; currentMoney++ ) {
//默认最小硬币数就是当前金额的本身
//举例：63元最多就是63个1元的硬币呗
int minCoins = currentMoney;
//遍历硬币面额数组，找到前边所能找到的最小硬币数加1
for( int coinKind = 0 ; coinKind < coins.length ; coinKind++ ) {
资源评论
