用实例解析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]; //金额数组，也就是备忘录数组

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

分享名称：用实例解析java动态规划算法中硬币找零问题-创新互联
文章地址：http://wjwzjz.com/article/dcgcdd.html