使用贪心算法解决“柠檬水找零”问题（吊炸天的解法）

柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为5美元。
顾客排队购买你的产品，一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：bills = [5,5,10,10,20]
输出：false解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
分析：
贪心算法中的局部最优解是什么意思？针对这道题，顾客付费20元，我们有两种找零的方案（10元+5元，3张5元），两种找零方案哪种对老板更有利呢？当然是找零一张10元一张5元了，因为5元零钱是万能的，既可以找零10元面额也可以找零20元面额。所以这道题针对“付费20元”这个局部场景，它的最优解就是先判断有没有10+5的零钱，如果没有，再判断有没有3*5的方案。

package od1;

/**
 * 柠檬水找零
 * 在柠檬水摊上，每一杯柠檬水的售价为5美元。
 * 顾客排队购买你的产品，一次购买一杯。
 * 每位顾客只买一杯柠檬水，然后向你付5美元,10元或20美元。你必须给每个顾客正确找零。
 * 注意，一开始你手头没有任何零钱。
 * 如果你能给每位顾客正确找零，返回true，否则返回false。
 * 原文地址：https://www.codernav.com/2850.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest34 {
    public static void main(String[] args) {
        boolean result = f(new int[]{5, 5, 5, 10, 5, 20, 5, 10, 5, 20});
        System.out.println(result);
    }

    private static boolean f(int[] bills) {
        // 5元零钱个数
        int five = 0;
        // 10元零钱个数
        int ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                ten++;
                five--;
            } else if (bill == 20) {
                if (ten > 0) {
                    ten--;
                    five--;
                } else {
                    five -= 3;
                }
            }
            // 核心代码：5元零钱够不够用，小于0说明不够找零
            if (five < 0) {
                return false;
            }
        }
        return true;
    }
}

贪心算法（greedy algorithm，又称贪婪算法）
是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心算法一般按如下步骤进行：
1、建立数学模型来描述问题。
2、把求解的问题分成若干个子问题。
3、对每个子问题求解，得到子问题的局部最优解。
4、把子问题的解局部最优解合成原来解问题的一个解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。