贪心算法的使用场景
- 给定一组数据，定义了限制值和期望值，在限定的条件下，期望值最大。
- 在对限制值同等贡献量条件下，选择对期望值贡献最大的数据
- 举几个例子验证弹性算法的正确性
几个经典的场景
分糖果
有N个大小不同的糖果，分给M个孩子，N>M，每个孩子对于糖果大小的需求不同,并且每个孩子得到一个糖果就能满足，请问如何分：
答：按照贪心算法，限制值是M，每个孩子一颗糖即相同期望值是一颗糖，我们想尽量满足更多的孩子，所以我们要先将最小的糖果分给对糖果的大小需求小的孩子
钱币找零
钱币有10，20，50，100的零钱，我们如何找零
答：由于找零所需的金额一定，即限制值是金额。我们希望相同纸币数的情况下多贡献金额，相同期望值是纸币数。所以我们先将大的找出去，在用零钱填补空缺。
空间覆盖
从N个空间选出尽量多不相交的区间见下图
答：我们选择尽量靠近左端且不与前面覆盖的端点，然后右边选择离左边尽量近的点给右边尽可能大的空间
huffman编码
用于压缩一段数据往往压缩的量在20~90%之间，原理在：https://time.geekbang.org/column/article/73188
后期完善