贪心算法
算法知识点
贪心算法（又称贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。其具有高效性和不稳定性，它可以非常迅速地获得一个解，但这个解不一定是最优解，即便不是最优解，也是最近似最优解的解。
贪心算法一般用来解决求最大或最小解。
解题步骤
1.分解：将原问题分解为若干个相互独立的阶段
2.解决：在每个相互独立的阶段进行贪心选择，求出局部最优解
3.合并：将各个阶段的解合并为原问题的解
算法题目来源
- 柠檬水找零 - 力扣（LeetCode）
算法题目描述
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
做题思路
我们拥有的钞票面值只可能是5美元、10美元、20美元三种：
5美元：与柠檬水价格相等，直接收下即可
10美元：多于柠檬水售价5美元，需要找回5美元，如果没有5美元则无法正确找零
20美元：多余柠檬水售价15美元，需要找回15美元，15美元可以是一个10美元的加一个5美元的也可以是三个5美元的，在找零时我们更倾向于第一种，因为5美元的找零场景比较多，我们需要尽可能保留5美元的钞票
代码
#include <stdio.h>
#include <string.h>
int main() {
int bills[100];
int i = 0, five = 0, ten = 0;
bool flag = true;
do {
scanf("%d", &bills[i]);
i++;
} while (getchar() != '\n');//换行结束输入
for (int j = 0; j < i; j++) {
if (bills[j] == 5) {
five++;//收到5美元，five加1
} else if (bills[j] == 10) {
if (five == 0) {
flag = false;//收到10美元，没有5美元的钞票，flag赋值为false
}
five--;
ten++;有5美元钞票，five减1，ten加1
} else {
if (five > 0 && ten > 0) {
five--;
ten--;//收到20美元，如果5美元和10美元都有，则five减1，ten减1
} else if (five >= 3) {
five -= 3;//如果5美元和10美元不是都有，但有三张以上5美元的，five减3
} else {
flag = false;//两个都没有，flag赋值为false
}
}
}
if (flag) {
printf("true");
} else {
printf("false");
}//输出结果
return 0;
}
运行结果
读书笔记
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。
