算法导论15.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

15.1-1

直接使用pre数组记录当下所有状态的转移过程。

算法DYNAMIC-PROGRAMMING-ACTIVITY-SELECTOR使用了一个三重嵌套循环，其时间复杂度为\(O(n^3)\)，而 算法GREEDY-ACTIVITY-SELECTOR的时间复杂度为\(\Theta(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
GEN-SOLUTION(pre, C, i, j)
  if C[i, j] == 0
    return ∅
  else
    return {a_k} ∪ GEN-SOLUTION(pre, C, i, k) ∪ GEN-SOLUTION(pre, C, k, j)


DYNAMIC-PROGRAMMING-ACTIVITY-SELECTOR(s, f, n)
  // pre 表示状态转移到何处。
  let pre[0 : n + 1, 0 : n + 1] and c[0 : n + 1, 0 : n + 1] be new tablges
  INSERT(s, +∞)
  for i = 0 to n
    c[i, i] = 0
    c[i, i + 1] = 0
  c[n + 1, n + 1] = 0
  for l = 2 to n + 1
    for i = 0 to n + 2 - l
      j = i + l - 1
        k = i + 1
        while k < j and f[k] <= s[j]
          if f[i] <= s[k] and c[i, k] + c[k, j] + 1 > c[i, j]
            c[i, j] = c[i, k] + c[k, j] + 1
            pre[i, j] = k 
          k = k + 1
  return GEN-SOLUTION(pre, C, 0, n + 1)

15.1-2

假设现在关于活动的开始时间\(s'\)和结束时间\(t'\)是按照开始时间进行排序的。

令\(S'_k=\{a_i\in S:s_i'\le f_k'\}\)。考虑证明：如果\(a'_m\)子问题是\(S_k'\)中最晚开始的活动，那么必定存在一个最优解\(A_k'\)，并且满足\(a'_m\in A_k'\)。

如果\(a_m'\in A_k'\)，那么不证自明；否则令\(a_n'\)是\(A_k'\)中最晚开始的活动，那么有\(s_n'\le s_m'\)。令\(B_k'=A_k'-\{a_n'\}\cup \{a_m'\}\)，由于\(a_n'\)和上一个活动不会产生交集，那么\(a_m'\)也不会和上一个活动产生交集，因此\(B_k'\)也是一个最优解。

因此，每次选择最晚开始的活动，这种贪心策略也是成立的。

15.1-3

当\(s=[1,8,10],f=[10,12,20]\)时，可以知道这种贪心策略是不正确的。使用这种贪心策略只能选择第\(2\)个活动，即\(\{8,12\}\)，因为这个活动的时间最短。而使用正确的贪心策略则会选择第\(1\)和\(3\)个活动。

15.1-4

首先假设所有活动已经按结束时间排序好。基本的贪心思想是，在保证当前活动按时召开的情况下，选择一个当前最晚结束的厅，将当前活动接入到这个厅即可，并更新这个厅最晚的结束时间。如果实在找不到满足条件的厅，那么就新开一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ACTIVITY-ARRANGER(s, f, n)
  let A be a new array
  count = 0
  // 使用一个二叉查找树T来存储三元组(f, hall)，分别代表编号为hall的厅中，最后一个活动的结束时间为f，这个二叉查找树将以f作为键。
  let T be a new ordered-set
  for i = 1 to n
    // 找到最晚能够早于s[i]结束的一个厅。
    get the greatest node x in T such that x.f <= s[i]
    // 找不到这样的厅，需要新开。
    if x == NIL
      INSERT(A, ∅)
      count = count + 1
      A[count] = A[count] ∪ {a_i}
      let p be a new node, p.f = f[i], p.hall = count
      INSERT(T, p)
    else
      DELETE(T, x)
      A[x.hall] = A[x.hall] ∪ {a_i}
      x.f = f[i]
      INSERT(T, x)
  return count, A

15.1-5

可以使用一个非常直接的动态规划算法来解决本问题。按照题目原本的要求，一个活动\(i\)可以接在一个活动\(j\)的后面当且仅当\(f[j]\le s[i]\)。那么以当前活动作为最后一个活动，以此作为动态规划的阶段。令状态\(g[i]\)表示以\(i\)为最后一个活动时，这样的安排可以得到最大的活动权值之和。考虑能够接在活动\(i\)前面每一个活动\(j\)的情况，可以写出\(g\)的状态转移方程：

\(g[i]= \left \{\begin{aligned} &0 & & \text{if}\quad i=0 \\ &\max_{0\le j< i,f[j]\le s[i]} \{g[j]+v[i]\} & & \text{if}\quad i\neq 0\\ \end{aligned}\right.\)

算法ACTIVITY-SELECTOR-VALUE'给出了具体的伪代码。由第6-8行的嵌套循环可知，这个算法的时间复杂度为\(O(n^2)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// a_0 = (0, 0, 0)，即第0个活动是没有价值的。
ACTIVITY-SELECTOR-VALUE'(s, f, v, n)
  // 已经假设所有活动按结束时间f进行排序。
  let g[0 : n], pre[1 : n] be new arrays
  g[0] = 0
  // p是取得最大值的下标。
  p = 0
  for i = 1 to n
    g[i] = 0
    j = 0
    while j < i and f[j] <= s[i]
      if f[j] <= s[i] and g[j] + v[i] > g[i] 
        g[i] = g[j] + v[i]
        pre[i] = j
      j = j + 1
    if g[i] > g[p]
      p = i
  A = {a_p}
  q = p
  while pre[p] != 0
    A = A ∪ {A_pre[p]}
    p = pre[p]
  return g[q], A