柠檬水找零

在柠檬水摊上，每杯柠檬水售价5元，顾客排队购买，一次买一杯。

每位顾客只买一杯，然后向你付5元、10元或20元。必须给每个顾客正确找零。

注意一开始你的手头没有任何零钱。

如果你能给每位顾客正确找零。则返回true，否则返回false。

贪心算法：遇到5直接收下；遇到10，退一张5块，收下10块；遇到20块，有两种决策，最优决策是找一张10块和一张5块，这就是贪心的核心思路。因为要尽可能避免5块钱被找出去，5块钱最万能。第二种决策就是找3张5块这是在第一种决策不行的情况再考虑的第二种情况。

上代码：

//17.柠檬水找零
public class LemonChange17 {
    public static void main(String[] args) {
        System.out.println(change(new int[]{5,5,10,20}));
        System.out.println(change(new int[]{5,10,10,20}));
    }
    //贪心算法
    public static boolean change(int[] bills){
        int five=0;
        int ten=0;
        for (int bill:bills){
            if (bill==5){
                five++;
            }else if (bill==10){
                if (five==0){
                    return false;
                }else {
                    five--;
                    ten++;
                }
            }else {
                if (ten>0&&five>0){//局部最优
                    five--;
                    ten--;
                }else if (five>=3){
                    five-=3;
                }else {
                    return false;
                }
            }
        }
        return true;
    }
}

结果：

true

false