floor($moneyNum / $faceValue);//做除数运算
$moneyNum -= intval($quotient * $faceValue);//减去已经找过的...这时候我们就需要用到贪心算法
贪心算法是指,在每一次情况下,都选择当前最优的解进行处理,
在这个场景里面,最优的解就应该是从大到小进行找零了,89块钱,先找最大面值的50块钱,然后找10块钱的,以此类推...动态规划
在上面的从大到小进行做除数运算,获得一个找零解之后,我们现在研究另一个问题:
当钞票金额只有3,5,需要找零11元时,你会发现上面的算法根本算不出结果,因为它不管从大到小进行除数找零,还是从小到大进行除数找零都不能找到结果...使其在面额为3,5,找零11元的情况下,被金额5"贪心迷惑",找2个金额5,导致算法无解
这个算法实现了在这种情况下,不贪心,不被眼前的2*5迷惑,为了"大局",舍弃了表面的最优
那么?...当面额只有1,30,50,找零90的情况下,根据贪心+规划算法,我们能得到50*1+30*1+1*10的情况,这需要用到12张钞票,但是实际情况我们只需要找30*3,3张钞票即可解决该问题.这代表着我们需要完全遍历所有能找零的方法