贪心算法的实例

贪心算法（Greedy Algorithm）是一种常用的算法思想，其基本思想是在每一步选择中都采取当前状态下最优的选择（贪心），从而希望能够导致全局最优解。下面将以几个实例为例，从多个角度分析贪心算法。

1. 零钱找零

面对一个给定的以及一定数量的纸币和硬币，给出一个总数，问如何使用这些钞票硬币，使得总数恰好等于所需的总数，并且要求使用的钞票硬币数量最少。

贪心策略：选择一个钞票硬币时，选择最大的金额，并且保证所选金额小于所需总数。并继续选择下一个金额最大的，直到所需总数为0为止。

比如，当我们需要找零41元时，我们可以采取以下策略：

选择最大面额的硬币25元，需找15元；

选择次大的面额的硬币10元，需找5元；

选择最小的硬币1元，需找4元；

此时，所用硬币数最少，共使用3个硬币。

此时，贪心算法得到了最优解，但是并不是所有情况下的结果就一定是最优解。

2. 活动安排问题

有许多需要在同一时间段使用同一场地的活动，给出每个活动的开始时间和结束时间，要求在同一时刻只能进行一个活动，问如何安排活动，能够尽可能多的活动得到它们的时间段。

贪心策略：按照活动结束时间的早晚排序，先选择结束时间最早的活动，并将该活动的结束时间设为当前时间点。然后，继续选择下一场能够在当前时间点开始的活动。

举个例子，我们有以下6个活动：

| 活动 | 开始时间 | 结束时间 |

|------|----------|----------|

| A | 1 | 4 |

| B | 3 | 5 |

| C | 0 | 6 |

| D | 5 | 7 |

| E | 3 | 8 |

| F | 5 | 9 |

按照结束时间从早到晚的顺序排序，分别为A、C、B、E、D、F。贪心算法的策略如下：

选择A活动，当前时间设为4；

选择C活动，当前时间设为6；

不能选择B活动，因为与C活动时间有重叠；

选择E活动，当前时间设为8；

不能选择D活动，与E活动时间有重叠；

选择F活动，当前时间设为9；

共选择4个活动。

同样的，在某些情况下，贪心算法并不总是能够得到最优解。

3. 背包问题

有一个可以承载重量为W的背包，有n个物品，每个物品的重量为wi，价值为vi，要求在保证不超过背包承载重量的前提下，选取一些物品，使得这些物品的价值之和最大。

贪心策略：按照每个物品的单位重量价值（vi/wi）从大到小排列，选择价值单位最大的物品加入背包中，直到完全不能再加入新的物品为止。

例如，有5个物品：装A、装B、装C、装D、装E，重量分别为2、2、6、5、4，价值分别为6、3、5、4、6，而背包的承重量W为10。我们将物品按照单位重量价值从高到低排序，并按照以上贪心策略进行选择，得到以下的结果：

选择装E，价值=6，重量=4，剩余重量=6；

选择装C，价值=5，重量=6，剩余重量=0；

共选择2个装备，总价值=11。

需要注意的是，在背包问题中，贪心算法依然并不总是能得到最优解。