内容简介:硬币找零问题是动态规划的一个经典问题,其中最少硬币找零是一个变种,本篇将参照上一篇01背包问题的解题思路,来详细讲解一下最少硬币找零问题。如果你需要查看上一篇,可以点击下面链接:下面让我们开始吧。给定4种面额的硬币1分,2分,5分,6分,如果要找11分的零钱,怎么做才能使得找的硬币数量总和最少。
硬币找零问题是动态规划的一个经典问题,其中最少硬币找零是一个变种,本篇将参照上一篇01背包问题的解题思路,来详细讲解一下最少硬币找零问题。如果你需要查看上一篇,可以点击下面链接: 详解动态规划01背包问题--JavaScript实现
下面让我们开始吧。
问题
给定4种面额的硬币1分,2分,5分,6分,如果要找11分的零钱,怎么做才能使得找的硬币数量总和最少。
分析
最少硬币找零问题,是为了求硬币的组合,所以一个大前提是硬币无限量供应。我们建立如下表格来分析问题:
其中每列用j表示零钱总额,每行i表示硬币面额。 T[i][j]
表示硬币个数,它是我们即将填入表格的数字。
在填写表格之前,我们需要先明确几个规则:
- 当填写第i行时,使用的硬币面额仅能是i以及小于i的面额。举个例子,比如我填写第0行,i=0,那么这一样只能使用面额为1分的硬币。当我填写第2行,i=2,那么可以使用1分,2分,5分三种面额的硬币。
- 当填写第j列时,表示当前需要使用硬币凑出的总额。比如j=6,表示需要使用硬币组合出总额为6分的情况。
1. i = 0
当我们只能使用面额为1分的硬币时,根据上面的规则,那么很显然,总额为几分,就需要几个硬币。即 T[i][j] = j
。
2. i = 1
当我们有1分和2分两种面额时,那么组合方式就相对多了点。
i=1 j = 1
:总额为1时,只能使用1分的面额。即填1。 i=1 j = 2
:总额为2时,可以使用2个1分的,也可以使用1个2分的。因为我们要求最少硬币,所以使用1个2分的。表格所表达的意思是硬币的数量,所以这里也填1。 i=1 j = 3
:总额为3时,可以使用3个1分的,也可以使用1个1分加1个2分。因此这里应该填2。 i=1 j = 4
:总额为4时,可以使用4个1分的,可以使用2个1分加1个2分,也可以使用2个2分。其中硬币最少的情况应该是2个2分。因此这里填2。 i=1 j = 5
:总额为5时,组合就更多了,但是聪明的你应该能想到使用2个2分加1个1分,可以实现最少硬币的需求。因此这里填3。
我们来看填写完上面5格后的情况:
建议你自己再纸上照着我这图画一个表格。接下来,别急着填表。我们要根据已有的数据,总结出 T[i][j]
的规律,然后通过填写剩余表格来验证。
我们将硬币面额使用数组coins[i]来表示,根据表格有 1分=coins[0], 2分=coins[1]。 当j<coins[i]时, T[i][j]
的值,应该等于它的同列,上一行,即使 T[i][j] == T[i-1][j]
。 比如我们从表中所看到的, T[1][1]==T[0][1]
。 当j>=coins[i]时,根据已有的 i=1行可以推出一个规律,令 a = 1+T[i][j-coins[i]]
, T[i][j]= min(T[i-1][j],a)
,即二者比较取最小值。可能一开始你看到这个关于a的公式,有点太突然,难以接受。稍微解释一下,当第i行,优先选择这一样的硬币,因为这一行的硬币面额最大,最有可能使得总硬币数量最少。因此 j-coins[i]
,就很好理解了,就是选择了这一行的硬币后,还剩下多少总额。举个例子,当i=1,j=3时,j-coins[1]=1。那么选择2分后,还剩余总额为1,这时候我们再定位到i=1,j=1,即T[1][1],它的值为1,再加上一个常数1,即得最终结果2。
再举例, i=1 j=5
。由于是从左到右填表的,所以i=1,j<5的表格都填完了。j-coins[i]=3,定位到 T[1][3]=2
,加上常数1,即得最后结果 T[1][5]=3
。
其实公式本身很短,也很好记。如果实在无法理解,建议先不用纠结。先最小化浏览器,不要看本篇剩余的内容。带着这个解题公式,自己在纸上,把这个表格填写完整,在填表分析的过程中就能慢慢理解了。
3. 剩余内容
按照上一步所提供的公式,其实所有的 T[i][j]
都可以填完了。如下表格。
建议先自己再纸上填表,填完了,再和我的图对比一下,看是否答案存在出入。
4.伪代码
以上的填表逻辑,使用伪代码表示如下
if(i == 0){ T[i][j] = j/coins[i]; //硬币找零一定要有个 最小面额1,否则会无解 }else{ if(j >= coins[i]){ T[i][j] = min(T[i-1][j],1+T[i][j-coins[i]]) }else{ T[i][j] = T[i-1][j]; } }
5. 寻找组合
至此,填完表格我们已经接近完成了。接下来要寻找从表格中寻找硬币组合。
与填表顺序相反,寻找组合从有下角开始。
首先需要明确的是如果 T[i][j] == T[i-1][j]
,那么就向上搜索。根据图来分析:
1.定位到 T[3][11]
,由于不存在 T[i][j] == T[i-1][j]
,所以不用向上搜索,确定选中一个 6分
硬币。 寻找组合的思路和填写T[i][j]的思路几乎是反过来的 。
2.选择一个6分硬币后,剩余的总额为11-6=5。因此定位到T[3][5]中。由于T[3][5]==T[2][5],因此看图中的蓝色箭头,向上搜索,直到 T[i][j] != T[i-1]
。
3.定位到T[2][5]中,此时coins[i]为5分。选中5分硬币只有,剩余的总额为5-5=0。
4.当j=0时,搜索结束。由上面步骤确定选中的硬币组合为:1个5分,1个6分。
代码
以上就是整个最少硬币找零问题的分析思路。最终代码使用 JavaScript 实现,如果你的 Sublime 支持纯 JavaScript,你可以直接复制黏贴代码,command + b 直接运行查看结果,然后修改输入变量,查看更多情况下的输出结果。
//动态规划 -- 硬币找零问题 function minCoins(coins,total,n){ var T = []; for(let i = 0;i<n;i++){ T[i] = [] for (let j=0;j<= total;j++){ if(j == 0){ T[i][j] = 0; continue; } if(i == 0){ T[i][j] = j/coins[i]; //硬币找零一定要有个 最小面额1,否则会无解 }else{ if(j >= coins[i]){ T[i][j] = Math.min(T[i-1][j],1+T[i][j-coins[i]]) }else{ T[i][j] = T[i-1][j]; } } } } findValue(coins,total,n,T); return T; } function findValue(coins,total,n,T){ var i = n-1, j = total; while(i>0 && j >0){ if(T[i][j]!=T[i-1][j]){ //锁定位置,确定i,j值,开始找构成结果的硬币组合。 其实根据这种计算方法,只需要考虑最右边那一列,从下往上推。 //console.log(T[i][j]); break }else{ i--; } } var s = []; //存储组合结果 while(i >= 0 && j > 0 ){ s.push(coins[i]); j=j-coins[i]; if(j <= 0){ break; //计算结束,退出循环 } //如果 i == 0,那么就在第 0 行一直循环计算,直到 j=0即可 if(i>0){ //console.log(i); while(T[i][j] == T[i-1][j]){ i--; if(i== 0){ break; } } } } console.log(s); //可以把数组s return 回去 } var coins = [1,2,5,6]; var total = 11 var n = coins.length console.log(minCoins(coins,total,n));
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
深入浅出数据分析
Michael Milton / 李芳 / 电子工业出版社 / 2009 / 88.00元
《深入浅出数据分析》以类似“章回小说”的活泼形式,生动地向读者展现优秀的数据分析人员应知应会的技术:数据分析基本步骤、实验方法、最优化方法、假设检验方法、贝叶斯统计方法、主观概率法、启发法、直方图法、回归法、误差处理、相关数据库、数据整理技巧;正文以后,意犹未尽地以三篇附录介绍数据分析十大要务、R工具及ToolPak工具,在充分展现目标知识以外,为读者搭建了走向深入研究的桥梁。 本书构思跌宕......一起来看看 《深入浅出数据分析》 这本书的介绍吧!