一、概述

1.设计思想

贪心算法通过一系列选择来得到问题的解，所做的每个选择都是当前状态下局部最好选择，即贪心选择。

贪心算法并不从整体最优上加以考虑，所做的选择只是在某种意义上的局部选择，在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果确实最优解的很好的近似解。

2.基本要素

（1）贪心选择性质

贪心算法所做的选择可以依赖以往所做过的选择，但绝不依赖将来所做的选择，也不依赖子问题的解。

（2）最优子结构性质

当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。

3.存在的问题

（1）不能保证求得的最后解是最佳的；
（2）不能用来求最大或最小解问题；
（3）只能求满足某些约束条件的可行解的范围。

4.算法比较

二、例题总结

1.活动安排问题

【问题描述】 设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源（如演讲会场等），而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和结束时间fi，如果选择了活动i，则它在半开区间[si,fi)与区间[sj,fj)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i和j是相容的，也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。

【算法设计】由于活动占用资源的时间没有限制，因此，选择最早结束时间作为贪心策略更加合理，目的是使剩余时间段最大化，以便安排尽可能多相容的活动。

【算法实现】

数组f中元素按结束时间非降序排列，若未按此序排列，可以用O(nlogn)做时间重排。

2.背包问题

【问题描述】 设背包容量为C，n个物品，物品价值和重量为v[i],w[i]。物品可以只装一部分。

【算法设计】不存在0-1要求，先装单价最贵的，再装单价次贵的，依此贪心策略一直进行下去，直到背包装满。

【算法实现】 O(nlogn)

3.最优装载问题

【问题描述】设有一轮船能装载的货物重量为C，有n个集装箱，重量为w[i]，问怎样可以装尽可能多的集装箱。

【算法设计】先装最轻的，再装次轻的，依此贪心策略一直进行下去，直到轮船装满。

【算法实现】 O(nlogn)

贪心算法