柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为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、把子问题的解局部最优解合成原来解问题的一个解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。
相关文章
