We are given n integers x1,x2, …, xn, where n is even. Suppose we group these n numbers into n/2 pairs and add up each of the pairs. The weight of this grouping is the maximum of these sums.
For example, if the input numbers are 5, 7, 8, -2, 6, 4, 5, 2 and if they are paired up as (5,-2), (7,4), (5,6), (2,8) then the sums of the 4 pairs are 3, 11, 11, and 10. The weight is the maximum of {3, 11, 11, 10} and is thus 11.
For each of the following sets of integers, find a way of grouping them into pairs so that the weight is minimized. In your answer, list out the grouping and then indicate the weight.
(a) 103, 24, 77, 65, 12, 108, 69, 25, 66, 83
(b) 83, 112, -16, 72, 161, 75, 152, -23, 77, 247
© 19, 81, 2, 41, 61, 59, 28, 69, 76, 88