优化问题
计算机科学中许多算法都是为了找到某些问题的最优解
例如，两个点之间的最短路径；能最好匹配一系列点的直线；或者满足一定条件的最小集合
找零兑换问题
一个经典案例是兑换最少个数的硬币问题
假设你为一家自动售货机厂家编程序，自动售货机要每次找给顾客最少数量硬币；假设某次顾客投进$1纸币，买了*37的东西，要找*63，那么最少数量就是： 2个quarter（*25）、 1个dime（*10）和3个penny（*1），一共6个
贪心策略解决找零兑换问题
人们会采用各种策略来解决这些问题， 例如最直观的“贪心策略”
一般我们这么做：
从最大面值的硬币开始，用尽量多的数量有余额的，再到下一最大面值的硬币，还用尽量多的数量，一直到penny（*1）为止
贪心策略Greedy Method
贪心策略
因为我们每次都试图解决问题的尽量大的一部分对应到兑换硬币问题，就是每次以最多数量的最大面值硬币来迅速减少找零面
“贪心策略”解决找零兑换问题， 在美元或其他货币的硬币体系下表现尚好
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: