算法导论14 Problems 答案

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

14-1

如果从节点\(s\)取\(t\)的路径最长化，那么子问题就相当于从\(s\)的后继节点\(u\)去到\(t\)的路径最长化，并且再添加上从\(s\)到\(v\)的路径。

子问题图就是\((V-\{s\},E-\{(s,v,w)\mid v \in V\})\).

令\(d(G,s,t)\)表示从图\(G=(V,E)\)中的\(s\)点到\(t\)点的最长路径，那么可以写出状态转移方程：

\[d(G,s,t)=\max_{(s,v,w) \in E}\{d((V-\{s\},E-\{(s,v,w)\mid v \in V\}),v,t)+w\}\]

其中，\(d(G,t,t)=0\)，因为不需要移动。

由于删除的点的集合数量是幂指增长的，并且可能每个顶点都有出边，因此这个算法的时间复杂度为\(O(2^{|V|}\cdot |E|)\)。

可以使用拓扑排序，优化上述状态转移方程，将其降低至\(O(|V|+|E|)\)的时间复杂度。此时不需要涉及对图的操作。

14-2

如果一个回文字符串两边拼上两个相同的字符，那么得到了一个新的回文字符串，其长度增加了\(2\)；如果一个字符串两边的字符串不相同，那么它的最长回文子序列一定是来自内部的子字符串。因此，\(w[i,j]\)的最优子结构是\(w[i+1,j-1],w[i+1,j],w[i,j-1]\)。令\(w[i,j]\)表示子字符串\(X[i:j]\)的最长回文子序列。那么可以写出\(w\)的状态转移方程：

\(w[i,j]= \left \{\begin{aligned} &0 & & \text{if}\quad i>j \\ &1 & & \text{if}\quad i=j \\ &w[i+1,j-1]+2 & & \text{if}\quad i<j\land X[i]=X[j]\\ &\max(w[i+1,j],w[i,j-1]) & & \text{if}\quad i<j\land X[i]\neq X[j]\\ \end{aligned}\right.\)

计算出表\(w\)的所有值即可。根据第4, 5行的2个嵌套循环不难得知，这个算法的时间复杂度为\(\Theta(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
24
25
26
27
28
29
LPS-SOLUTION(X, m)
  let w[1 : m, 1 : m] be new table
  for l = 1 to m
    w[i, i] = 1
  for l = 2 to m
    for i = 1 to m - l + 1
      j = i + l - 1
      if X[i] == X[j]
        w[i, j] = w[i - 1, j + 1] + 2
      else
        w[i, j] = max{w[i - 1, j], w[i + 1, j]}
  n = w[1, m]
  let a[1 : n] be new array
  lp = 1
  rp = m
  lq = 1
  rq = n
  while lp <= rp
    if X[lp] == X[rp]
      a[lq] = a[rq] = X[lp]
      lq = lq + 1
      rq = rq - 1
      lp = lp + 1
      rp = rp - 1
    else if w[lp, rp] == w[lp + 1, rp]
      lp = lp + 1
    else
      rp = rp - 1
  return n and a

14-3

首先需要对这些点的\(x\)坐标进行排序，那么我们可以考虑把这一些点拆分成两部分，组成两条不相交的有向路径，但是公用起点和终点。那么令\(d[i, j]\)表示这两条不相交路径的终点分别为\(i\)和\(j\)时（假设\(i> j\)），从起点到点\(i\)和从起点到点\(j\)这两条路径的最短长度之和。

那么对于状态\(d[i,j]\)而言，考虑每次添加一个右边的点\(i+1\)进来。添加时，这个点可以添加到\(i\)后面，那么变成状态\(d[i+1,j]\)，也可以添加到\(j\)后面，变成状态\(d[i+1,i]\)。

那么，可以写出\(d\)的状态转移方程：

\(d[i,j]= \left \{\begin{aligned} &\text{dis}(p_i,p_j) & & \text{if}\quad i=2\land j=1 \\ &d[i-1,j] + \text{dis}(p_i,p_j) & & \text{if}\quad i > 2\land j < i - 1 \\ &\min_{k=1}^{i-2} \{d[i-1,k] + \text{dis}(p_k,p_j)\} & & \text{if}\quad i > 2\land j = i - 1 \\ \end{aligned}\right.\)

因此，最终还需要使两条路线指定相同的终点，那么最终答案为

\[\min_{i=1}^{n-2}\{d[n-1,i]+\text{dis}(p_n,p_{n-1})+\text{dis}(p_n,p_i)\}\]

子程序POINT-DISTANCE(A, B)用于计算两个点的欧几里得距离，此处忽略实现过程。

假设计算两点间距离POINT-DISTANCE(A, B)的时间复杂度为\(O(1)\)。观察程序BITONIC-TSP第6行的嵌套循环不难得知，这个程序的时间复杂度为\(\Theta(n^2)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BITONIC-TSP(p, n)
  sort p by their x coordinate
  let d[1 : n - 1, 1 : n - 1] be new table
  d[2, 1] = POINT-DISTANCE(p[2], p[1])
  if n == 2
    return d[2, 1] * 2 
  for i = 3 to n - 1
    for j = 1 to i - 2
      d[i, j] = d[i - 1, j] + POINT-DISTANCE(p[i - 1], p[i])
    d[i, i - 1] = ∞
    for j = 1 to i - 2
      d[i, i - 1] = min{d[i - 1, j] + POINT-DISTANCE(p[j], p[i])}
  min-dis = ∞
  for i = 1 to n - 2
    min-dis = min{min-dis, d[n - 1][i] + POINT-DISTANCE(p[n - 1], p[n]) + POINT-DISTANCE(p[i], p[n])}
  return min-dis

14-4

由于最后一行字符并不考虑后面的空格，因此我们考虑从后往前进行考虑。那么最优子问题就是将单词序列\(l_i,l_{i+1},\dots,l_n\)打印出来需要的额外空格立方之和。

如果后面这些单词只需要一行打印出来，那么就没有额外的空格（因为第一行就是最后一行）。否则，枚举\(j\ge i\)，并且单词序列\(l_i,l_{i+1},\dots,l_j\)都能在一行打印出来，余下的空格数立方和与打印\(l_{j+1},l_{j+2},\dots,l_n\)时的最优决策时的值相加即可。

令状态\(f[i]\)表示将单词序列\(l_i,l_{i+1},\dots,l_n\)打印出来需要的额外空格立方之和，其中\(\displaystyle{s[i,j]=j-i+\sum_{k=i}^j l_k}\)表示如果打印单词序列\(l_i,l_{i+1},\dots,l_j\)时所需要的字符数。那么可以写出状态转移方程\(f\)：

\(f[i]= \left \{\begin{aligned} &0 & & \text{if}\quad s[i,n]\le M \\ &\min_{i\le j\le n, s[i,j]\le m}\{ (M-s[i,j])^3+f[j+1]\} & & \text{if}\quad s[i,n]\le M \\ \end{aligned}\right.\)

如果\(s[i,j]\)的任意值可以以\(\Theta(1)\)的时间计算出来，那么根据程序PRINTING-NEATLY-SOLUTION的第5行循环，可以观察出这个算法的时间复杂度为\(\Theta(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
24
25
26
CAL-CHARACTERS(l, r, S)
  return S[r] - S[l - 1] + r - l

PRINTING-NEATLY-SOLUTION(L, n, M)
  let f[1 : n], s[0 : n], c[0 : n] be new arrays
  s[0] = 0
  for i = 1 to n
    s[i] = s[i - 1] + L[i]
  for i = n downto 1
    if CAL-CHARACTERS(i, n, S)
      f[i] = 0
      c[i] = ∞
    else
      f[i] = ∞
      for j = i to n
        w = CAL-CHARACTERS(i, j, S)
        if w <= M
          if f[j + 1] + (M - w) ^ 3 < f[i]
            f[i] = f[j + 1] + (M - w) ^ 3
            c[i] = j + 1
  let p be new array
  i = 1
  while i <= n
    INSERT(p, i)
    i = c[i]
  return f[1] and c

14-5

a

这里的子问题设计成：已经处理完了字符串\(X[1:i],Y[1:j]\)时所需要的最小花费。

按照这6种操作的定义，直接从前往后转移即可。

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
26
EDIT-DISTANCE(X, Y, m, n, QC, QR, QD, QI, QT, QK)
  let d[0 : m, 0 : n] be new table with ∞
  d[0, 0] = 0
  for i = 0 to m
    for j = 0 to n
      c1 = c2 = c3 = c4 = c5 = ∞
      if i > 0 and j > 0
        // 复制
        if X[i] == Y[j]
          c1 = d[i - 1, j - 1] + QC
        // 替换
        c2 = d[i - 1, j - 1] + QR
      // 删除
      if i > 0
        c3 = d[i - 1, j] + QD
      // 插入
      if j > 0
        c4 = d[i, j - 1] + QI
      // 旋转
      if i >= 2 and j >= 2 and X[i] == Y[j - 1] and Y[j] == X[i - 1]
        c5 = d[i - 2, j - 2] + QT
      d[i, j] = min{c1, c2, c3, c4, c5}
  // 终止
  for i = 0 to m - 1
    d[m, n] = min{d[m, n], d[i, n] + QK}
  return d[m, n]

b

禁用旋转和终止操作，也就是令\(Q_T=Q_K=+\infty\)。

仅仅使用剩下四个操作，有\(Q_C = -1,Q_I= Q_D = 2,Q_R = 1\)。

其中，插入和删除操作对应两个字符含有空格的规则；复制对应两个字符相同的规则；替换对应两个字符不相同的规则。

最终，如下调用- EDIT-DISTANCE(X, Y, m, n, -1, 1, 2, 2, QT, QK)这个程序即可得到最大的分数，注意前面有一个负号。

14-6

对于每一个员工\(x\)，他可以进行两种决策：要么出席，要么缺席。以\(x\)为子树的所有员工决策满足最优子结构性质。以\(x\)为子树的出席最优决策，取决于\(x\)的所有孩子的子树的最优决策。

如果\(x\)出席，那么\(x\)的下属都不出席；如果\(x\)不出席，那么\(x\)的下属出不出席并没有限制，那么选择其中最优的一个选择即可。

因此，分别令\(f_{\text{attend}}(x),f_{\text{absent}}(x)\)表示当\(x\)出席/缺席时，以\(x\)为子树能够获得的最大分数和。那么不难写出状态转移方程为：

\(\begin{aligned} &f_{\text{attend}}(x)=\sum_{y \text{ is child of }x} f_{\text{absent}}(y)\\ &f_{\text{absent}}(x)=x.\texttt{rating}+\sum_{y \text{ is child of }x} \max\{f_{\text{absent}}(y),f_{\text{attend}}(y)\}\\ \end{aligned}\)

因此如果根节点为\(r\)，最终结果为根节点\(\max\{f_{\text{absent}}(r),f_{\text{attend}}(r)\}\)。

由于每个节点恰好都被遍历了一次，并且其余操作都是常数操作，因此整个算法的时间复杂度为\(\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
26
27
28
29
30
31
32
33
PLANNING-A-COMPANY-PARTY(x)
  attend, absent = PLANNING-NOW(x)
  m = max{attend, absent}
  let A be new array
  PLANNING-GET-SOLUTION(x, A, m == attend)
  return m and A 

PLANNING-NOW(x)
  if x == NIL
    return 0 and 0
  attend = x.rating
  absent = 0
  p = x.left-child
  while p != NIL
    x, y = PLANNING-NOW(p)
    attend = attend + y
    absent = absent + max{x, y}
    p = p.right-sibling
  x.attend = attend
  x.absent = absent
  return attend and absent

PLANNING-GET-SOLUTION(x, A, isattend)
  if x == NIL
    return 
  if isattend
    INSERT(A, x)
  p = x.left-child
  while p != NIL
    if isattend == True
      PLANNING-GET-SOLUTION(p, A, False)
    else
      PLANNING-GET-SOLUTION(p, A, p.attend >= p.absent)

14-7

a

考虑状态\(d[i,j]\)表示是否存在一条从\(v_0\)开始，长度为\(i\)，最终到达节点\(j\)的路径。并且，这一条路径的权值和sigma[1 : i]完全匹配。如果长度为\(i-1\)的路径是匹配的，并且符号相同，那么长度为\(i\)的路径也必定是匹配的。

那么不难写出关于\(d\)的状态转移方程：

\(d[i,j]= \left \{\begin{aligned} &1 & & \text{if}\quad i=0 \land j=v_0\lor i>0\land (\exists u\in V,(u,j)\in E\land\sigma(u,j)=\sigma_i\land d[i-1,u]=1) \\ &0 & & \text{if}\quad i=0 \land j\neq v_0\lor i>0\land\lnot (\exists u\in V,(u,j)\in E\land\sigma(u,j)=\sigma_i\land d[i-1,u]=1) \\ \end{aligned}\right.\)

最终，如果\(G\)是采用邻接表实现的，那么为了方便转移，此时使用图\(G\)的转置\(G^T\)进行转移。那么根据程序VITERBI-PATH第5行的内循环可以得知，进行一次的时间为\(\Theta(|E|)\)，外加外循环\(\Theta(k)\)，最终整个算法的时间复杂度为\(\Theta(k\cdot |E|)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
VITERBI-PATH(G, v0, sigma, k)
  let d[0 : k, 1 : |V|], prev[0 : k, 1 : |V|] be new tables with 0
  let GT be transpose graph of G
  d[0, v0] = 1
  for i = 1 to k
    for u = 1 to |V|
      for each v in GT.Adj[u]
        if d[i - 1, v] == 1 and GT.sigma(u, v) == sigma[i]
          d[i, u] = 1
          prev[i, u] = v
  for q = 1 to |V|
    if d[k, q] == 1
      let sol[0, k] be new array
      sol[0] = v0
      for i = k downto 1
        sol[i] = q
        q = prev[i][q]
      return sol
  return NO-SUCH-PATH

b

只需要多记录一个状态参数prob[i, j]，表示这条路径如果存在的最大概率，转移时只需要顺带维护状态值即可。

由于只是多新建了一个表，单次转移的过程仍然是\(\Theta(1)\)，因此整个算法的时间复杂度仍为\(\Theta(k\cdot |E|)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
VITERBI-PATH'(G, v0, sigma, k)
  let d[0 : k, 1 : |V|], prev[0 : k, 1 : |V|], prob[0 : k, 1 : |V|] be new tables with 0
  let GT be transpose graph of G
  d[0, v0] = 1
  prob[0, v0] = 1
  for i = 1 to k
    for u = 1 to |V|
      for each v in GT.Adj[u]
        if d[i - 1, v] == 1 and GT.sigma(u, v) == sigma[i]
          d[i, u] = 1
          if prob[i - 1, v] * GT.p(u, v) > prob[i, u]   
            prob[i, u] = prob[i - 1, v] * GT.p(u, v)
            prev[i, u] = v
  for q = 1 to |V|
    if d[k, q] == 1
      let sol[0, k] be new array
      sol[0] = v0
      for i = k downto 1
        sol[i] = q
        q = prev[i][q]
      return sol
  return NO-SUCH-PATH

14-8

a

由于\(n>1\)，因此如果在第\(1\)列，有两个选项朝下方选择：正下方或者是右下方；如果是在第\(n\)列，那么可以选择正下方或者是左下方；否则，左下方，正下方，右下方都可以选择。无论在哪一行哪一列，都至少有\(2\)个选项选择，因此一个图像的接缝数的渐进增长满足\(\Omega(2^m)\)，即指数级别。

b

令状态\(f[i,j]\)表示已经删除了前\(i\)行的一个像素，其中删除的第\(i\)行的像素为\(j\)时，已经累积的破坏度。

那么按照题意，每一个状态仅能从\(f[i-1,j-1],f[i-1,j],f[i-1,j+1]\)三个之一转移而来，不难写出状态转移方程：

\(f[i,j]= \left \{\begin{aligned} &d[i,j] & & \text{if}\quad i=1 \\ &\min\{f[i-1,j],f[i-1,j+1]\}+d[i,j] & & \text{if}\quad i>1 \land j = 1\\ &\min\{f[i-1,j-1],f[i-1,j]\}+d[i,j] & & \text{if}\quad i>1 \land j = m\\ &\min\{f[i-1,j-1],f[i-1,j],f[i-1,j+1]\}+d[i,j] & & \text{if}\quad i>1 \land 1 < j < m\\ \end{aligned}\right.\)

删完最后一行的像素后，得到最终结果：

\[\min_{j=1}^n\{f[m,j]\}\]

由于可以转移的状态最多为\(3\)个，因此根据第5, 6行的嵌套循环可知算法IMAGE-COMPRESSION的时间复杂度为\(\Theta(n,m)\)。

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
26
27
28
29
30
IMAGE-COMPRESSION(A, d, m, n)
  let f[0 : k, 1 : |V|], prev[0 : k, 1 : |V|] be new tables
  for j = 1 to n
    f[1, j] = d[1, j]
    prev[1, j] = j
  for i = 2 to m
    for j = 1 to n
      c1 = c2 = c3 = ∞
      if j > 1
        c1 = f[i - 1, j - 1] + d[i, j]
      c2 = f[i - 1, j] + d[i, j]
      if j < m
        c3 = f[i - 1, j + 1] + d[i, j]
      c = min{c1, c2, c3}
      f[i, j] = c
      if c == c1
        prev[i, j] = j - 1
      else if c == c2
        prev[i, j] = j
      else
        prev[i, j] = j + 1
  q = 1
  for j = 1 to n
    if f[m, j] < f[m, q]
      q = j
  let sol[1 : m] be new array
  for j = m downto 1
    sol[j] = q
    q = prev[m, q]
  return f[m, q] and sol

14-9

为了方便描述和编写这个算法，数组\(L\)末端会添加一个新元素\(n\)，也就是字符串\(s\)的长度。

这个问题的子问题是将字符串\(s[L[i-1]+1:L[j]]\)按照\(L[i:j]\)所展示的那样划分，如果这个划分是最优的，那么由最优子结构的问题组合成的原问题也是最优的。

令\(f[i,j]\)表示将\(s[L[i-1]+1:L[j]]\)按照\(L[i:j]\)划分时，所需要的最小代价。那么考虑从\([i,j)\)中间某个点\(k\)进行切分。可以写出关于\(f\)状态转移方程：

\(f[i,j]= \left \{\begin{aligned} &d[i,j] & & \text{if}\quad i=j \\ &\min_{k=i}^{j-1}\{f[i,k]+f[k+1,j]\}+L[j]-L[i-1] & & \text{if}\quad i<j\\ \end{aligned}\right.\)

那么最终将整个字符串划分的最小代价为\(f[1,m]\)。

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
26
27
28
29
BREAKING-STRING-GEN-SOL(sol, prev, i, j)
  if i == j
    return
  INSERT(sol, prev[i, j])
  BREAKING-STRING-GEN-SOL(sol, prev, i, prev[i, j])
  BREAKING-STRING-GEN-SOL(sol, prev, prev[i, j] + 1, j)

BREAKING-STRING(S, L, n, m)
  //为了方便，在下标m+1处多添加一个元素n，虽然已经溢出了。 
  L[m + 1] = n
  let f[1 : k, 1 : m + 1] be new table with ∞
  let prev[1 : k, 1 : m + 1] be new table
  m += 1
  for i = 1 to m
    f[i, i] = 0
  for l = 2 to m
    for i = 1 to m - l + 1
      j = i + l - 1
      tmp = ∞
      q = i
      for k = i to j - 1
        if f[i, k] + f[k + 1, j] + L[j] - L[i - 1] < tmp
          tmp = f[i, k] + f[k + 1, j] + L[j] - L[i - 1]
          q = k
      f[i, j] = tmp
      prev[i, j] = q
  let sol be a new array
  BREAKING-STRING-GEN-SOL(sol, prev, 1, m)

14-10

这道题的题意似乎并不太清晰，需要多添加另外\(2\)个假设：

  1. 每一年投资得到的利息，不能用于下一次投资。也就是说，每一年投资额恒为\(10000\)美元。
  2. 每年年末支付\(f_1,f_2\)时，是额外支付的，并不从投资的本金中支付。

a

假设存在一个最优的投资计划，并且第\(y_1\)到第\(y_2\)年中，该投资计划保持不变。那么假设第\(y_1\)年开始前，对第\(i\)个投资投资了\(d_i\)美元，那么到第\(y_2\)年结束时，得到的钱为\(\displaystyle{\sum_{i=1}^n\sum_{j=y_1}^{y_2} d_i r_{ij}}\)。

可以知道\(\exists 1\le p\le n,\forall 1\le i\le n\)，使得\(\displaystyle{\sum_{j=y_1}^{y_2} r_{pj}\ge\sum_{j=y_1}^{y_2} r_{ij}}\)均成立。

因此，将这个投资计划的投给第\(i\)个投资产品的钱转移到投给第\(p\)个投资产品，那么在第\(y_1\)年到第\(y_2\)年得到的钱将会更多。

也就是有：

\[\sum_{i=1}^n\sum_{j=y_1}^{y_2} d_i r_{ij}\le \sum_{i=1}^n\sum_{j=y_1}^{y_2} d_i r_{pj}=d\sum_{j=y_1}^{y_2} r_{pj}\]

最终，如果存在一种最优的方案是投资多个产品，那么通过上述剪切-粘贴技术可以将这个投资方案转化成一个更优的单一投资产品方案。

b

按照题目14-10-a的结论，如果今年的投资方案是最优的，要么就是从上一年同一个投资产品最优的方案转移而来，此时仅产生少量的费用\(f_1\)，要么是从投资其它产品的最优方案直接迁移所有资金到当前产品，此时产生同样的资金转移费用。因此，单一状态\(f[i,j]\)的最优解来自于这\(n\)个子问题的最优解。

c

令\(f[i,j]\)表示第\(i\)年结束时（假设第\(i+1\)年不继续，那么就不付手续费），最终得到的钱的总数（其中\(d=10000\)）。

那么不难写出状态转移方程：

\(f[i,j]= \left \{\begin{aligned} &d\cdot r_{j1} & & \text{if}\quad i=1 \\ &\max\{f[i-1,j]-f_1,\max_{k=1}^n\{f[i-1,k]\}-f_2\} +d\cdot r_{ji}& & \text{if} \quad i>1\\ \end{aligned}\right.\)

由此可得到最终答案为

\[\max_{j=1}^{n} \{f[10,j]\}\]

那么可以写出如下算法INVESTMENT-STRATEGY，注意到第4行的嵌套循环是一个二重循环，因此可以知道整个算法的时间复杂度为\(\Theta(n\cdot y)\)。

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
26
INVESTMENT-STRATEGY(r, n, d = 10000, y = 10)
  let f[1 : y, 1 : n], prev[1 : y][1 : n] be new table with 0
  for j = 1 to n
    f[1, j] = d * r[j, 1]
  for i = 2 to y
    pt = 1
    for j = 1 to n
      if f[i - 1, j] > f[i - 1, pt]
        pt = j
    for j = 1 to n
      if f[i - 1, j] - f1 > f[i - 1, pt] - f2
        f[i, j] = f[i - 1, j] - f1 + d * r[j, i]
        prev[i, j] = j
      else
        f[i, j] = f[i - 1, pt] - f2 + d * r[j, i]
        prev[i, j] = pt
  pt = 1
  for j = 1 to n
    if f[y, j] > f[y, pt]
      pt = j
  let sol[1, y] be new array
  q = pt
  for i = y downto 1
    sol[i] = q
    q = prev[i, q]
  return f[y, pt] and sol

d

如果添加了这个限制，那么对于当前状态\(f[i,j]\)，如果一开始投资的金额超过了\(15000\)的美元，那么需要涉及到资金分拆的问题，新生成的子问题将会涉及到多个使用分拆后的资金进行投资的问题，由此子问题数量将会急剧上升，原来我们所设计的最优子结构将不会再成立。

14-11

考虑将每一个月的月终视为动态规划的一个阶段，子问题则是上一个月剩下的机器数量。

令\(f[i, j]\)表示第\(i\)个月结束后，在仓库内部剩下的机器数量为\(j\)时，所需要交付出的最少成本。

对于每个状态\(f[i, j]\)，它可以从\(0 \sim j + d_i\)这些状态转移而来，因为就算不生产，为达到当前数量，上限只能会是\(j+d_i\)。

那么不难写出状态转移方程：

\(f[i,j]= \left \{\begin{aligned} &\text{cost}(j+d_i,m,c) & & \text{if}\quad i=1 \\ &\min_{k=0}^{\min\{j+d_i,D\}} \{f[i-1,k]+\text{cost}(j-k+d_i,m,c)\}& & \text{if} \quad i>1\\ \end{aligned}\right.\)

其中，\(\text{cost}(n,m,c)=\max\{n-m,0\}\cdot c\)表示这个月生产\(n\)个机器时带来的额外成本。

由此可得到最终答案为

\[\min_{j=1}^{D} \{f[n,j]\}\]

那么可以写出如下算法INVENTORY-PLANNING，注意到第5, 6, 7行的嵌套循环，其中第\(6\)个循环的循环上限最大为\(D\)，因此可以知道整个算法的时间复杂度为\(O(nD^2)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
COST(n, m, c)
  return max{n - m, 0} * c

INVENTORY-PLANNING(d, n, m, c, h)
  D = sum(d)
  let f[1 : n, 0 : D] be new table with ∞
  for j = 0 to D
    f[1, j] = cal(j + d[1], m, c) + h[j]
  for i = 2 to n
    for j = 0 to D
      for k = 0 to min{j + d[i], D}
        f[i, j] = min{f[i, j], f[i - 1, k] + COST(j - k + d[i], m, c) + h[j]}
  return min{f[n, 0], f[n, 1], ..., f[n, D]}

14-12

考虑将每一个位置视作是动态规划的一个阶段。

令\(f[i, j]\)表示已经考虑签约了前\(j\)个位置的球员，已经花费了\(j\)，得到的最大VORP之和。

对于每个状态\(f[i, j]\)，一共有\(P+1\)个策略：分别从\(P\)个球员中选择一个；或者是在这个位置上不招球员。

那么可以写出状态转移方程：

\(f[i,j]= \left \{\begin{aligned} &0 & & \text{if}\quad i=0\land j=0 \\ &\max\{f[i-1,j],\max_{1\le k\le P,\text{cost}[i,k]\le j} \{f[i-1,j-\text{cost}[i,k]]+\text{vorp}[i,k]\}\} & & \text{if}\quad 1\le i\le n \\ &-\infty & & \text{otherwise} \\ \end{aligned}\right.\)

可以得到最终答案为

\[\max_{j=1}^{X} f[N,j]\]

那么可以写出如下算法SIGNING-FREE-AGENT-BASEBALL-PLAYERS，注意到第4, 5, 7行的嵌套循环，循环大小分别恒为\(N,X+1,P\)，因此整个程序的时间复杂度为\(\Theta(NXP)\)。

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
26
// 这里同样假设X是10万的整数，并且cost[i, j], vorp[i, j]表示第i个位置第j个人的信息。
// 这两个表的下标范围为cost[1 : N, 1 : P], vorp[1 : N, 1 : P]。
SIGNING-FREE-AGENT-BASEBALL-PLAYERS(cost, vorp, N, P, X)
  let f[0 : N, 0 : X] be new table with -∞
  let prev[0 : N][0 : X] be new table with 0
  f[0, 0] = 0
  for i = 1 to N
    for j = 0 to X
      f[i, j] = f[i - 1, j]
      for k = 1 to P
        if cost[i, k] <= j and f[i - 1,j - cost[i, k]] + vorp[i, k] > f[i, j]
          f[i, j] = f[i - 1,j - cost[i, k]] + vorp[i, k]
          prev[i, j] = k
  max_vorp = -∞
  now_cost = 0
  for j = 0 to X
    if f[N, j] > max_vorp
      max_vorp = f[N, j]
      now_cost = j
  let sol be new array
  j = now_cost
  for i = N downto 1
    if prev[i, j] != 0
      INSERT(sol, (i, k))
      j = j - cost[i, k]
  return max_vorp, now_cost and sol