由于考试算法中用到贪心时需要先证明其正确性才能使用，所以本人学习了一下贪心算法的证明方法并作此笔记。

首先，在网上找到的贪心策略证明有：

考察一个问题的最优解,证明可修改该最优解,使得其从贪心选择开始,然后用数学归纳法证明每一步都可以通过贪心选择得到最优解

1,假定首选元素不是贪心选择所要的元素,证明将首元素替换成贪心选择所需元素,依然得到最优解；

2,数学归纳法证明每一步均可通过贪心选择得到最优解

 

本人对此的理解就是当前你有一个最优解，然后我们将这个最优解分为两块，前边和后边都是对应集合的最优解，我们最后边的最优解，从下一步选择开始使用贪心选择对其中的元素进行替换，之后仍然是最优解，这就证明了贪心的正确性。

注：要特别注意，贪心是求得一个最优解，而不是求得唯一的最优解。

（1）如果bm = bi，择仍然为最优解

（2）如果bm != bi,则需要证明去除bi,加入bm仍然构成最优解即可。

 

下边我们来用贪心的一个经典例子，活动安排来讲解此问题。

1.首先，我们有一个最优解A，对这个最优解进行讨论

2.对这里边的第一个活动，若他是结束时间最早的活动，符合贪心，若不是，可以将第一个活动改为结束最早的活动（一定可以替换），所以当k = 1时，贪心正确。

3.推广到k > 1,对A的子集，我们已经选择可k个活动，构成Ak,下边我们进行第 k+1 个活动的选择，（注意，我们选择的前提是与Ak相容，贪心算法时选择的也是相容的最早结束的活动），原本我们的最优解扣去Ak后剩余B，对第k+1个活动的选取，我们选取结束最早的且相容的活动bm，若bm在B中，显然贪心成立，若bm不在b中，我们取出B中结束最早的活动bi,将bm加入其中，仍然不改变最优解的性质，贪心算法得到证明。

 

注：贪心算法证明的要义  1.选择一个普通的最优解  2.用贪心选择来替换其中的某一步选择时最优解性质不变，数学归纳证明其正确性。