高级算法设计与分析 学习笔记12 贪心算法

首先我们来解决一个经典的活动选择问题：

s代表开始时间，f代表结束时间

可以看到这是一个动态规划的算法

现在，我们要把这个解决办法转换成一个贪心算法

直觉上讲，每次都选最先结束的可以留下最多的资源

当然开始之前先要把所有时间按照结束时间排个序（nlgn就行）这样比较方便。

那么贪心算法究竟是什么结构呢？

背包问题

0/1背包问题就是物品要么不放，要么全放进来。分数背包可以只放一部分。可见0/1背包用贪心不是最优的，但分数可以。

哈夫曼编码

使用哈夫曼编码可以节约空间

实际上哈夫曼编码的过程也是一个贪心过程。