【算法】贪心法

0.何为贪心？

贪心算法就是，每次选择的时候，都选择局部最优的那个选择。

1.贪心算法的不稳定性

兑换硬币问题

已知有5种不同面值的硬币：1元、2角5分、1角、5分、1分，现在想兑换6角7分，且得到的硬币最少。

从最大的的开始选，2个2角5分，之后1个1角，1个5分，2个1分，这就是最优解啦！

如果面值为：1角1分、5分、1分，现在想兑换1角5分，且得到的硬币最少。

应用贪心算法，得到1枚1角1分，4枚1分，显然不是最优解，因为还可以换3个5分钱硬币。

这表明，贪心算法并不是时时刻刻都有效的。若有效，需要满足两个条件：

1. 一个优化问题的优化解包含剩余子问题优化解。
2. 一个优化问题的全局优化解可以通过局部优化选择得到。

证明方法可以有：归纳法、交换论证法。后者的意思是，

交换论证主要的思想也就是先假设存在一个最优的算法和我们的贪心算法最接近，
然后通过交换两个算法里的一个步骤(或元素)，得到一个新的最优的算法，同时
这个算法比前一个最优算法更接近于我们的贪心算法，从而得到矛盾，原命题成立。

——博客园链接

2.活动选择问题

给定一系列活动$a_1,a_2,\cdots,a_n$，每个活动有起始、终止时间$s_i,f_i$。在一个只能容纳一个活动的场所里展开这些活动，求一个活动数最多的安排方案。

贪！我们每次选择具有最小结束时间的活动。下面给出三个引理及之证明方法：

所以该方法可行。