• 贪心方法的基本要素
  • 贪心准则选取：整体最优解可以通过一系列局部最优的选择（贪心选择）来达到
  • 最优子结构
  • 贪心算法正确性的数学归纳法证明：利用数学归纳法，证明每一步的贪心选择可以得到整体最优解。
  • 与动态规划算法的区别：动态规划还有另一个特征：重叠子问题
• 具体算法
  • 活动安排、最优装载、哈夫曼编码、单源点最短路径、最小生成树（最小代价生成树）、多机调度
  • 掌握上述具体算法相应的贪心策略基本要素，比如最优子结构式，伪代码描述，正确性证明等
  • 给定输入，能追踪算法的求解过程，

例子：有 5元、2元、1元，要支付 13 元，如何使得张数最少？

前面的动态规划也出现了这个例子，其求解方法为：

dp=[]

def solve(n):
    global dp
    if len(dp)<n+1:
        dp=[-1 for i in range(n+1)]
    if n<0:
        return 0
    if n==0:
        return 1
    if dp[n]==-1:
        dp[n]=solve(n-1)+solve(n-2)+solve(n-5)
    return dp[n]

但从直觉来看，显然应该先选择 2 张 5 元，然后再选择 1 张 2 元，1 张 1元。即先使用面额大的来填充数额。这种就是贪心算法。

贪心算法最重要的就是 启发规则（Heuristic rule）：就是我们应该用什么标准去判断 “最”。比如上面问题的启发规则就是面额最大。

活动安排问题

再看一个例子：有 $n$ 个活动，其 start time 和 finish time 分别为 $[s_i,f_i]$，同一时刻只能安排一个活动，问如何安排才能进行最多的活动。

可以作为启发规则的只有：开始时间、持续时间、结束时间。简单排除法可知，只有结束时间有可能作为启发规则。于是可以写出如下代码：

def printMaxActivities(s , f ): 
    n = len(f) 
    print "The following activities are selected"
  
    # The first activity is always selected 
    i = 0
    print i, 
  
    # Consider rest of the activities 
    for j in xrange(n): 
  
        # If this activity has start time greater than 
        # or equal to the finish time of previously 
        # selected activity, then select it 
        if s[j] >= f[i]: 
            print j, 
            i = j 
  
# Driver program to test above function 
s = [1 , 3 , 0 , 5 , 8 , 5] 
f = [2 , 4 , 6 , 7 , 9 , 9] 
printMaxActivities(s , f) 

下面简单证明一下为什么要用结束时间：

• 设活动按结束时间排序为 ${1,2,\cdots,n}$；
• 根据启发规则，最优安排 $A$ 以活动 $1$ 开头；
• 如果有另一个活动 $B$ 优于 $A$ 但以 $k\neq 1$ 开头，那么，显然，我们可以令 $A= (B-{k}) \cup {1}$，即用 1 代替 k；
• 这样，$A$ 与 $B$ 同样优，说明不可能存在比 $A$ 更优的安排；
• 递推可证后续活动同样适用启发规则。

复杂度：排序需要 $O(n\log n)$，安排活动需要 $O(n)$

单源点最短路径