贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

贪心算法两个基本要素的证明

1. 贪心选择性质
   首先你需要想好要用怎样的贪心策略，按什么样的顺序排列，从大的一边贪心还是小的一边。然后你随意举出问题的一个解，并假设这个解就是问题的最优解。然后如果这个解已经包含了贪心选择策略的第一个元素，则它直接满足贪心选择的最优解。如果不包括的话，你就将这个解中的一个元素替换为从贪心选择开始（也就是以你的贪心选择策略开始的第一个元素）。完了之后证明替换后的这个解也是该问题的一个最优解。这样就证明了问题具有贪心选择性质。
2. 最优子结构性质
   将你第一个贪心选择的元素从解集合中去掉。同时将问题的规模缩小，把这个从解集合去掉的元素也从问题的条件中去掉，把它带来的收益或者代价也从问题的限制中去掉。这样问题就缩小为比原问题更小的规模。之后你去证明，这个缩小的解集合是这个缩小的问题的解。这个问题就具有最优子结构性质

以活动安排为例

1. 贪心选择性质
   　 假设E是所有活动
   　 那么A包含于E，且A是该活动安排问题的一个最优解
   　 假设A的第一个活动是k
   　 假设k = 1，那么A就是以贪心选择开始的最优解
   　 假设k ≠ 1，那么设B = {A-{k}}∪{1} 即把A的第一个选择k去掉换成是1
   　 在这个情况下 B 的数量等于 A-1+1
   　 则B也是该问题的一个最优解
2. 最优子结构性质
   假设首先将1加进A中，即活动1是最优解的第一个活动
   那么问题就变成了求E中所有与活动1相容的最大子集合
   假设A是原问题最优解，那么A’ = A - {1}就是新的问题
   E’ = {i∈E，si>f1} 即求剩下活动中的最大相容子集的最优解
   反证法
   假设A’不是这个新问题的最优解，这个新问题存在一个最优解B’且B’活动数大于A’
   那么B’+{1} = B （B的活动数大于A） 的这个解也会是原问题 E 的最优解
   自相矛盾

另一个例子可以看
…背包问题

贪心选择与动态规划方法的区别