算法导论15.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 3.4k 阅读时长 ≈ 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\)。

假设问题\(S_1\)的一个最优解为选择补给点\(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_{y_1}\)也是\(S_{x_1}\)的一个子问题，因此\(S_{x_1}\)求出的解必定不会严格优于\(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\)中的一个区间\([l_j,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