16.1 活动选择问题

伪代码递归贪心算法

//输入：两个数组s和f，表示活动的开始和结束时间
//输入：下标k指出要求解的子问题S[k]，以及问题规模n
//返回：S[k]的一个最大兼容活动集
//假定输入的n个活动已经按结束时间的单调递增顺序排列好
RECURSIVE-ACTIVITY-SELECTOR(s,f,k,n)
//结束时间相同的活动可以任意排列
//为了方便算法初始化，添加一个虚拟活动a[0]，其结束时间f[0]=0,这样子子问题S[0]就是完整的活动集S
//求解原问题即可调用RECURSIVE-ACTIVITY-SELECTOR(s,f,0,n)
  m = k + 1
  //查找S[k]中最早结束的活动
  while m ≤ n and s[m] < f[k]
    m = m + 1
  //循环检查a[k+1],a[k+2],..,a[n]，直至找到第一个与a[k]兼容的活动a[m]，此活动满足s[m]≥f[k]
  if m ≤ n
    return {a[m]}URECURSIVE-ACTIVITY-SELECTOR(s,f,m,n)//返回{a[m]}与RECURSIVE-ACTIVITY-SELECTOR(s,f,m,n)返回的S[m]的最大子集的并集
  else return Φ//已经检查了S[k]中的所有活动，未找到与a[k]兼容者，返回Φ

算法的执行过程

alt alt

伪代码迭代贪心算法

//变量k记录了最近加入集合A的活动的下标，对应递归算法中的活动a[k]
//
GREEDY-ACTIVITY-SELECTOR(s,f)
  n = s.length
  A = {a[1]}//选择活动a[1]，将A的初值设置为只包含此活动
  k = 1//将k的初值设为此活动的下标
  //查找S[k]中最早结束的活动
  for m = 2 to n
    if s[m] ≥ f[k]//检查活动的开始时间s[m]是否不早于最近加入到A中的活动的结束时间f[k]
      A = A ∪ {a[m]}//如果活动a[m]是兼容的，将其加入A中
      k=m//将k设置为m
  return A

16.1-2

Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

alt

Solution

果我们想象时间以相反的方式运行，这与原始问题完全相同，因此它产生了一个最佳解决方案，原因基本相同。它是贪婪的，因为我们在每一步都做出了最漂亮的选择。

16.2 贪心算法原理

16.2-6

Show how to solve the fractional knapsack problem in O(n) time.

alt

Solution

首先计算每个项目的价值，定义为其价值除以其权重。我们使用如下递归方法，找到中值项，这可以在线性时间内完成，如第9章所示。然后将其值超过中位数的所有项目的权重相加，称之为M。如果M超过W，那么我们知道分数背包问题的解决方案在于从这个集合中获取项目。换句话说，我们现在正在解决大小为n/2的输入上的分数背包问题。另一方面，如果权重不超过W，则必须解决输入n/2个低值项的分数背包问题，最大权重为W − MW−M。T（n）表示算法的运行时间。因为我们可以解决在恒定时间内只有一个项目的问题，所以运行时的递归是T（n）=T（n/2）+cn和T（1）=d，这给出了O（n）的运行时间。

16.3 赫夫曼编码

字符编码问题

编码示例的二叉树表示

解码过程需要前缀码的一种方便的表示形式，以便我们可以容易地截取开始码字。一种二叉树表示可以满足这种需求，其叶结点为给定的字符。字符的二进制码字用从根结点到该字符叶结点的简单路径表示，其中0意味着"转向左孩子"，1意味着"转向右孩子"。下图给出了两个编码示例的二叉树表示。注意，编码树并不是二叉搜索树，因为叶结点并未有序排列，而内部结点并不包含字符关键字。

alt alt

构造赫夫曼编码

HUFFMAN(C)
  n = |C|
  Q = C//用C中字符初始化最小优先队列Q
  //反复从队列中提取两个频率最低的节点x和y，将它们合并为一个新节点z，替代它们
  for i = 1 to n-1
    allocate a new node z
    z.left = x = EXTRACT-MIN(Q)//结点z将x作为其左孩子
    z.right = y = EXTRACT-MIN(Q)//将y作为其右孩子
    z.freq = x.freq + y.freq//z的频率为x和y的频率之和
    INSERT(Q,z)
  return EXTRACT-MIN(Q)//返回队列中剩下的唯一节点——编码树的根节点

赫夫曼算法的执行过程

alt alt

16.3-3

What is an optimal Huffman code for the following set of frequencies, based on the first 88 Fibonacci numbers? a:1b:1c:2d:3e:5f:8g:13h:21 Can you generalize your answer to find the optimal code when the frequencies are the first n Fibonacci numbers?

基于前88个斐波那契数，以下频率组的最佳哈夫曼码是什么？

a:1b:1c:2d:3e:5f:8g:13h:21

当频率是前n个斐波那契数时，你能概括你的答案来找到最佳代码吗？