【MagO第四期】贪心算法经典例题：货币问题
01
贪心算法思想
贪心算法又称贪婪算法。贪心算法的思想是问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只是做出局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法之货币问题：根据人们生活常识，我们到商店里买东西需要找零钱时，当前有面值分别为100 元、50 元、20 元、10 元、5元、1元, 5角, 2角、1角的人民币。收银员总是先给我们最大面值的，要是不够再找面值小一点的，直到找完为止。这就是一个典型的贪心选择问题。
02
“货币支付问题”
现有面值分别为1,5,10,50,100元的纸币，其面值纸币对应的数量分别为5,2,2,3,5张纸币。问若要支付k元，则至少需要多少张纸币？
03
思路分析
求解最优化问题的两个关键要素：贪心选择性质+最优子结构
（1）贪心选择性质：进行选择时，直接做出在当前问题中看来最优的选择，而不必考虑子问题的解；
（2）最优子结构：如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质
我们只需要遵循“优先使用面值大的纸币”即可。（在纸币数量充足的情况下）
（1）尽可能多的使用100元（即最大的）；
（2）余下部分尽可能多的使用50元；
（3）余下部分尽可能多的使用10元；
（4）余下部分尽可能多的使用5元；
（5）余下部分使用1元；
04
参考代码
05
“找零钱的问题”
假如老板要找给我99元钱，他有面值分别为25，10，5，1元的硬币。为了找给我最少的硬币数，那么他是不是该这样找呢？先看看该找多少个25元的，99／25＝3，好像是3个，要是给4个的话，我还得再给老板一个1元的硬币，我不干。那么老板只能给我3个25元，由于还少给我24元，所以还得给我2个10元的硬币和4个1元的硬币。
思路与上题类似，每一步都优先给出大面值的硬币，直至找满。（这里无需考虑硬币数量是否充足）
06
项目练习
通过上面两题，相信大家已经此类用贪心算法解决货币找零问题有了更深的了解。对于类似题目，你能自己完成吗？橙子OJ上还有一个题目 “吝啬的老板”，也类似贪心算法中的货币问题，赶紧试着完成吧！
王大锤是个吝啬的饭店老板，饭店每天要消耗20桶油，买好油价格很贵。所以他都尽可能的买便宜的油。总共有a个油贩子，每个人每天可以提供价格为 Pi 元的 Ni 桶油。请问王老板每天买油最少要花多少钱？（ 所有油贩子提供的油绝对超过王大锤饭店每天的消耗量。）
尝试一下，自己解题吧：
https://oj.coding61.com/problem/%E8%B4%AA%E5%BF%831
还是没有思路？那么可以看一下讲解视频吧：