概念
贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。所以贪心就避免了为求得整体最优解而枚举各种方案所耗费的时间。
注意
- 不能保证贪心所得出的解是整体最优的
- 不能用来求最大解和最小解问题
- 只能求满足某些约束条件的可行解的范围
举例
找零钱问题：商品价格为m元，给了n元，需找零(n - m)元，现有人民币数额为1角、2角、5角、1元、2元、5元、10元、20元、50元、100元，要求使用的人民币张数最少。
- 思路
将所有金额及其被使用的张数存入集合中，从大到小遍历集合，若金额恰好小于找零，则该金额张数加一，找零减去对应金额。- 代码
public static Set<Entry<Double, Integer>> function(double m, double n) { double d = n - m; TreeMap<Double, Integer> rmbMap = new TreeMap<Double, Integer>(); rmbMap.put(100.0, 0); rmbMap.put(50.0, 0); rmbMap.put(20.0, 0); rmbMap.put(10.0, 0); rmbMap.put(5.0, 0); rmbMap.put(2.0, 0); rmbMap.put(1.0, 0); rmbMap.put(0.5, 0); rmbMap.put(0.2, 0); rmbMap.put(0.1, 0); while (d >= 0.1) { rmbMap.put(rmbMap.floorKey(d), rmbMap.get(rmbMap.floorKey(d)) + 1); d -= rmbMap.floorKey(d); } return rmbMap.entrySet(); }
