=== Problem B  activity selection ===
instance (already sorted by finish time):
  i     1   2   3   4   5   6   7   8   9  10
  s     0   2   1   5   4   8   7  10   9  12
  f     3   4   6   7   9  11  12  13  14  16
  d     3   2   5   2   5   3   5   3   5   4
  c     2   2   4   2   4   4   4   4   4   2
  earliest finish time -> {a1, a4, a6, a10}, size 4
  earliest start time  -> {a1, a5, a9}, size 3
  shortest duration    -> {a2, a4, a6, a10}, size 4
  fewest conflicts     -> {a1, a4, a6, a10}, size 4
  brute force over all 1024 subsets -> optimum size 4, e.g. {a1, a4, a6, a10}

=== Problem C  minimizing maximum lateness ===
  earliest deadline first:
    J1: p=3 finishes at   3, deadline   6, lateness  -3
    J2: p=2 finishes at   5, deadline   8, lateness  -3
    J3: p=1 finishes at   6, deadline   9, lateness  -3
    J4: p=4 finishes at  10, deadline   9, lateness   1
    J5: p=3 finishes at  13, deadline  14, lateness  -1
    J6: p=2 finishes at  15, deadline  15, lateness   0
    max lateness = 1
  shortest processing time first:
    J3: p=1 finishes at   1, deadline   9, lateness  -8
    J2: p=2 finishes at   3, deadline   8, lateness  -5
    J6: p=2 finishes at   5, deadline  15, lateness -10
    J1: p=3 finishes at   8, deadline   6, lateness   2
    J5: p=3 finishes at  11, deadline  14, lateness  -3
    J4: p=4 finishes at  15, deadline   9, lateness   6
    max lateness = 6
  brute force over all 720 orders -> optimum 1, attained by 20 of them

=== Problem D  Huffman on the machine log ===
  merge 1:   1 +   4 =   5
  merge 2:   5 +   8 =  13
  merge 3:  12 +  13 =  25
  merge 4:  15 +  22 =  37
  merge 5:  25 +  37 =  62
  merge 6:  38 +  62 = 100
  the tree (internal nodes in brackets, leaves as symbol:freq):
    (100)
       0-R:38
       1-(62)
          0-(25)
             0-F:12
             1-(13)
                0-(5)
                   0-Q:1
                   1-X:4
                1-P:8
          1-(37)
             0-D:15
             1-W:22
  sym  freq  code        len  freq*len
   R    38  0            1       38
   W    22  111          3       66
   D    15  110          3       45
   F    12  100          3       36
   P     8  1011         4       32
   X     4  10101        5       20
   Q     1  10100        5        5
  B(T) by summing over the leaves          = 242 kbit
  B(T) by summing the internal node labels = 242 kbit
  fixed-length (3 bits, 7 symbols)         = 300 kbit
  saving = 58 kbit = 19.33%
  round trip: "RRWDRFPRWXQDR" -> 34 bits -> "RRWDRFPRWXQDR"  OK

=== Problem E  the knapsack, capacity 10 ===
  item  v   w   v/w
     1   7   3  2.333
     2   6   3  2.000
     3   9   5  1.800
     4   9   5  1.800
  fractional greedy:  item1 x1.00  item2 x1.00  item3 x0.80  -> value 20.20
  0-1 greedy by density: item1 item2 -> value 13, weight used 6
  the dynamic-programming table c[i][w]:
      w =   0   1   2   3   4   5   6   7   8   9  10
  i = 0     0   0   0   0   0   0   0   0   0   0   0
  i = 1     0   0   0   7   7   7   7   7   7   7   7
  i = 2     0   0   0   7   7   7  13  13  13  13  13
  i = 3     0   0   0   7   7   9  13  13  16  16  16
  i = 4     0   0   0   7   7   9  13  13  16  16  18
  0-1 optimum by dynamic programming = 18, taking item3 item4
  brute force over 16 subsets = 18 (mask 12)
  greedy loses 5 of 18 = 27.8% of the 0-1 optimum
