算法导论14 Problems 答案

发表于 更新于 分类于 阅读次数： 本文字数： 7.4k 阅读时长 ≈ 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,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}(pi,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.$

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

子程序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

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

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

令状态$f[i]$表示将单词序列$li,l{i+1},\dots,ln$打印出来需要的额外空格立方之和，其中$\displaystyle{s[i,j]=j-i+\sum{k=i}^j lk}$表示如果打印单词序列$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.$

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

由于可以转移的状态最多为$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

假设存在一个最优的投资计划，并且第$y1$到第$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$年得到的钱将会更多。

也就是有：

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

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]}-f2} +d\cdot r{ji}& & \text{if} \quad i>1\
\end{aligned}\right.$

由此可得到最终答案为

那么可以写出如下算法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+di,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$个机器时带来的额外成本。

由此可得到最终答案为

那么可以写出如下算法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.$

可以得到最终答案为

那么可以写出如下算法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