算法导论15.2 Exercises 答案

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

15.2-1

令$m$为当前满足$\dfrac{v_m}{w_m}$最大的物品编号，假设存在一个最优解其解向量$x$满足如下条件：$\exists j,1\le j\le n,j\neq m$，并且有$x_j>0\land x_m< w_j$，那么构造一个新的解向量$x’$，其中$x_m’=x_m+\min{x_j,w_m-x_m},x_j’=x_j-\min{x_j,w_m-x_m}$，那么解$x$相对解$x’$所增加的价值为

$\begin{aligned}
\Delta &= (x_m’-x_m)\cdot\dfrac{v_m}{w_m}+(x_j’-x_j)\cdot\dfrac{v_j}{w_j}\
&=\min{x_j,w_m-x_m}\cdot\left(\dfrac{v_m}{w_m}-\dfrac{v_j}{w_j}\right)\
&>0
\end{aligned}$

那么由$x’$构造出了一个更优的解$x$，因此这个问题满足贪心选择性质。

15.2-2

令状态$f[i, j]$表示前$i$个物品至多重量和为$j$时，最大的总价值。对于当前状态，第$i$个物品有两种决策：取或者是不取。如果不取，那么相当于从状态$f[i-1,j]$转移而来；如果取，那么相当于从$f[i-1,j-w_i]$处取一个物品$i$转移而来，并且从中择优转移。因此不难写出如下状态转移方程：

$f[i,j]=
\left {\begin{aligned}
&0 & & \text{if}\quad i=0 \
&f[i-1,j]& & \text{if} \quad i>0 \land j< w_i\
&\max{f[i-1,j],f[i-1,j-w_i]+v_i}& & \text{if} \quad i>0 \land j\ge w_i\
\end{aligned}\right.$

因此最终答案为$f[n,W]$。

算法0-1-KNAPSACK-PROBLEM给出了具体的实现过程。第2-3行的嵌套循环说明这个算法的时间复杂度为$O(n\cdot W)$。

1
2
3
4
5
6
0-1-KNAPSACK-PROBLEM(w, v, n, W)
  let f[0 : W] be a new array by 0
  for i = 1 to n
    for j = W down to w[i]
      f[j] = max{f[j], f[j - w[i]] + v[i]}
  return f[W]

15.2-3

直接贪心选择价值最大的物品即可，算法0-1-KNAPSACK-PROBLEM'给出了具体的过程。

证明，假设一个解$S$包含了物品$(w_j,v_j)$，并且不包含物品$(w_i,v_i)(i< j)$，那么构造一组解$S’=S-{(w_j,v_j)}\cup {(w_i,v_i)}$。可以发现这个解的价值比$S$更大，因为价值增加了$v_i-v_j$，而且重量还减少了
$w_j-w_i$，这说明这个解更优，并且仍然是满足条件的。

由此，这个贪心算法是成立的。

1
2
3
4
5
6
7
8
9
// 假设物品已经按照重量从小到大排序，此时价值是从大到小排序的。
0-1-KNAPSACK-PROBLEM'(w, v, n, W)
  f = 0
  for i = 1 to n
    if w[i] > W
      break
    W = W - w[i]
    f = f + v[i]
  return f

15.2-4

假设整条路的情况用一个长度为$n+1$的数组$X$表示。道路上有$n$个补给点以及起点和终点，$X[1]$表示起点和下一个补给点的距离，$X[n + 1]$表示终点和最后一个补给点的距离，其余$n-1$个元素表示$n-1$对元素间的距离。

这道题使用的贪心思想是：尝试尽量到达下一个补给点（或者是终点），直到发现以当前水量不足以达下一个点了，才开始装水。

当选定好一个补给点$p$后，接下来的所有路可以视为一个同样的子问题。令子问题表示$S_i=X[i:n+1]$，那么原问题为$S_1$。

假设问题$S1$的一个最优解为选择补给点$T={x_1,x_2,x_3,\dots,x_m}$，按顺序列出，并且距离起点最远不超过$m$的补给点为$y_1$，并且有$x_1< y_1$。那么考虑证明可以构造出一个最优解，使得$y_1$是第$1$个选择的补给点。考虑如此证明：如果$x_1=y_1$，那么证明完成；否则，构造解$T’={y_1,x_2,x_3,\dots,x_m}$，可以发现$T’$和$T$的集合大小相同。一方面，由于$y_1>x_1$，从$y_1$出发可以更快的到达$x_2$，因此这个解是成立的；另一方面，子问题$S{y1}$也是$S{x1}$的一个子问题，因此$S{x1}$求出的解必定不会严格优于$S{y_1}$的解。因此整个贪心算法是成立的，具体实现由算法GEN-STOP-POINT给出。

1
2
3
4
5
6
7
8
9
10
11
12
GEN-STOP-POINT(X, n, m)
  A = ∅
  rest = m
  for i = 1 to n + 1
    if X[i] > m
      return ∅
    if X[i] > rest
      A = A ∪ {i - 1}
      rest = m - X[i]
    else
      rest = rest - X[i]
  return A

15.2-5

假设这些点$x_i$已经按照顺序排好序。那么证明：这个问题的一个最优解$S$满足：$S$中的所有区间的左端点是${x}$中的某些点。

假设解$S$中的一个区间$[lj,l_j+1]$满足$x{i-1}<l_j<x_i$，考虑区间$[x_i,x_i+1]$与其相比。可以知道，区间$[l_j,x_i)$并没有覆盖到任何点。考虑区间$(l_j+1,x_j+1]$，如果这个区间上没有点，那么区间$[x_i,x_i+1]$
和$[l_j,l_j+1]$覆盖的点是完全一样的；如果这个区间上有点，那么区间$[x_i,x_i+1]$不仅覆盖了$[l_j,l_j+1]$已经覆盖的所有点，还多覆盖了一部分点。因此无论那种情况，区间$[x_i,x_i+1]$都是比$[l_j,l_j+1]$更好的选择。故原结论成立。

并且，不难证明$S$中的所有区间两两不相交。因此我们可以给出一种算法：将最左边的点作为起点，向右延长一个单位。然后删除这个区间内的所有点，再在剩下的点中进行同样的操作。算法GEN-INTERVALS给出了详细过程。

1
2
3
4
5
6
7
8
9
10
// 由于所有区间的长度都是1，因此仅返回所有区间的左端点。
GEN-INTERVALS(X, n)
  RANDOMIZED-QUICKSORT(X, 1, n)
  left = -∞
  let A be a new array
  for i = 1 to n
    if left + 1 < X[i]
      left = X[i]
      INSERT(A, X[i])
  return A

$\star$ 15.2-6

本题的做法和问题9-3相似。假设数组$A$表示物品的列表，$A[i].w$与$A[i].v$分别表示第$i$个物品的重量和价值，那么按照值$\dfrac{A[i].v}{A[i].w}$作为关键字，将$A[i].w$作为权值，对数组$A$进行划分。最终的划分结果得出了一个下标$p$，在$p$右边的物品可以全部取完，物品$p$则按重量取完，在$p$左边的物品不取。

因此，算法FRACTION-KNAPSACK-PROBLEM2的行为和问题9-3-c的算法MEDIAN-WEIGHT一致，它们都是以$O(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
34
35
36
37
// 判断物品q的单位价值是否比p大。
ITEM-LE(p, q)
  return p.v * q.w < p.w * q.v

ITEM-PARTITION-WEIGHTED(A, p, r)
  s = 0
  x = A[r]
  i = p – 1
  for j = p to r – 1
    if ITEM-LE(A[j], x)
      i = i + 1
      exchange A[i] with A[j]
    else
      s = s + A[j].w
  exchange A[i + 1] with A[r]
  return i + 1, s + A[i + 1].w

ITEM-RANDOMIZED-PARTITION-WEIGHTED(A, p, r)
  i = RANDOM(p, r)
  exchange A[r] with A[i]
  return ITEM-PARTITION-WEIGHTED(A, p, r)

// 假设数组A中的每个元素都包含属性w和v，分别代表重量和价值，与原来的一致。
FRACTION-KNAPSACK-PROBLEM2(A, n, W)
  p = 1
  r = n
  while p < r
    q, nw = RANDOMIZED-PARTITION(A, p, r)
    if nw >= W
      p = q
    else
      r = q - 1
      W = W - nw
  sum = nw * (A[p].v / A[p].w)
  for i = p + 1 to n
    sum = sum + A[p].v
  return sum

15.2-7

算法CAL-PAYOFF给出了整个过程，基本思想是将两个数组排序，然后直接计算值$\displaystyle{M=\prod_{i=1}^n a_i^{b_i}}$并返回即可。

正确性说明：由于此时求的$M$值是乘积，那么对$M$求对数后，相当于是求$\displaystyle{S=\lg M=\sum_{i=1}^n b_i\lg a_i}$的最大值。由于$a_i$是正数，因此$\lg a_i$是非负的，令$a_i’=\lg a_i$。

假设一个解$A$中，$a_i’$和$b_i$配对，$a_j’$和$b_j$配对，并且有$a_i’<a_j’,b_i>b_j$，那么此时这两对数对$A$的贡献为$a_i’b_i+a_j’b_j$。考虑将这两对数中的$b$交换，得到一个新解$A’$，此时这两队数的贡献为$a_i’b_j+a_j’b_i$。

可以发现，解$A’$相比解$A$的花费变化为$a_i’b_j+a_j’b_i-a_i’b_i-a_j’b_j=(a’_j-a_i’)(b_i-b_j)>0$。这说明解$A’$比解$A$更优。因此，这种贪心方法是正确的。

1
2
3
4
5
6
7
8
// 假设物品已经按照重量从小到大排序，此时价值是从大到小排序的。
CAL-PAYOFF(A, B, n)
  RANDOMIZED-QUICKSORT(A, 1, n)
  RANDOMIZED-QUICKSORT(B, 1, n)
  payoff = 1
  for i = 1 to n
    payoff = payoff * POW(A[i], B[i])
  return payoff