算法笔记_048:找零问题（Java）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记_048:找零问题（Java），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2076字，纯文字阅读大概需要3分钟。
内容图文
目录
1 问题描述
现需找零金额为n，则最少需要用多少面值为d1 < d2 < d3 < ... < dm的硬币？（PS：假设这m种面值d1 < d2 < d3 < ... < dm的硬币，其中d1 = 1，且每种硬币数量无限可得）
2 解决方案
2.1 动态规划法
本文编码思想参考自《算法设计与分析基础》第三版，具体讲解如下：
具体代码如下：
package
com.liuzhen.chapter8;
public
class
ChangeMaking {
public
void getChangeMakingN(int[] coinType,int n){
int[] minNumber = newint[n+1]; //初始化后，所有元素均为0，其中minNumber[0] = 0，表示无须找零int[] tempMinJ = newint[n+1]; //tempMinJ[0]在此处无含义for(int i = 1;i <= n;i++){
int j = 0;
int tempJ = -1; //用于h获取minNumber[i]最小值中当前新使用的硬币面值数组下标int temp = Integer.MAX_VALUE; //计算当前minNumber[i]最小值，初始化int类型最大值while(j < coinType.length && i >= coinType[j]){
if(minNumber[i-coinType[j]] + 1 < temp){
temp = minNumber[i-coinType[j]] + 1;
tempJ = j;
}
j++;
}
minNumber[i] = temp;
tempMinJ[i] = tempJ;
}
System.out.println("给定硬币面值种类依次为：");
for(int i = 0;i < coinType.length;i++)
System.out.print(coinType[i]+" ");
System.out.println("\n找零大小从1到"+n+"的最少硬币组合数目为：");
for(int i = 1;i < minNumber.length;i++)
System.out.print(minNumber[i]+" ");
System.out.println("\n对应找零大小从1到"+n+"新增的硬币数组下标为：");
for(int i = 1;i < tempMinJ.length;i++)
System.out.print(tempMinJ[i]+" ");
System.out.println("\n对应找零大小从1到"+n+"新增的硬币数组下标对应的硬币面值为：");
for(int i = 1;i < tempMinJ.length;i++)
System.out.print(coinType[tempMinJ[i]]+" ");
System.out.println("\n\n找零大小为"+n+"的硬币组合最少数目为："+minNumber[minNumber.length-1]);
System.out.print("找零大小为"+n+"的硬币组合最少数目对应的硬币面值依次为：");
int needN = n;
int minJ = tempMinJ.length-1;
while(needN > 0){
System.out.print(coinType[tempMinJ[minJ]]+" ");
needN = needN - coinType[tempMinJ[minJ]];
minJ = needN;
}
}
publicstaticvoid main(String[] args){
ChangeMaking test = new ChangeMaking();
int[] coinType = {1,3,4};
test.getChangeMakingN(coinType, 6);
}
}
运行结果：
给定硬币面值种类依次为：
1 3 4
找零大小从1到6的最少硬币组合数目为：
1 2 1 1 2 2
对应找零大小从1到6新增的硬币数组下标为：
0 0 1 2 0 1
对应找零大小从1到6新增的硬币数组下标对应的硬币面值为：
1 1 3 4 1 3
找零大小为6的硬币组合最少数目为：2
找零大小为6的硬币组合最少数目对应的硬币面值依次为：3 3
参考资料：
1.算法设计与分析基础（第3版） Anany Levitin 著 潘彦 译
原文：http://www.cnblogs.com/liuzhen1995/p/6432749.html
内容总结
以上是互联网集市为您收集整理的算法笔记_048:找零问题（Java）全部内容，希望文章能够帮你解决算法笔记_048:找零问题（Java）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。