我目前正在读的算法设计手册和我卡在这个练习。你能帮助我吗？

I'm currently reading The Algorithm Design Manual and I'm stuck on this exercise. Could you help me out please?

径的2n实数作为输入的序列。设计为O（n log n）的算法， 分割数为n个对，与属性的分区最小化 一对中的最大总和。例如，假设我们得到的数字（1,3,5,9）。 可能的分区是（（1,3），（5,9）），（（1,5），（3,9）），和（（1,9），（3,5））。这对 总和为这些分区是（4,14），（6,12），和（10,8）。因此，第三个分区具有 10作为它的最大总和，这是最低超过三个分区。

Take a sequence of 2n real numbers as input. Design an O(n log n) algorithm that partitions the numbers into n pairs, with the property that the partition minimizes the maximum sum of a pair. For example, say we are given the numbers (1,3,5,9). The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and ((1,9),(3,5)). The pair sums for these partitions are (4,14), (6,12), and (10,8). Thus the third partition has 10 as its maximum sum, which is the minimum over the three partitions.

我从一些例子的猜测是，该解决方案是这样的：

My guess from some examples is that the solution looks like this:

# in pseudo ruby code
a = [1,3,5,9]
pairs = []
while !a.empty?
    pairs << [a.shift, a.pop]  # [a.first, a.last]
end
pairs

但我不能证明这一点。 感谢您的帮助，

But I can't prove it. Thanks for your help,

约翰·

推荐答案

该算法，因为当x 0 ，X 1 ，... X 2N 是排序列表，总有一个包含一个最优解（x 0 中，x 2n个）。

The algorithm works because when x0, x1, ... x2n is the sorted list, there is always an optimal solution that contains (x0, x2n).

证明：

考虑任何最佳的解决方案，它确实的没有的包含（X 0 ，X 2N ）。它必须包含对（X 0 ，X 一）和（x B ，X 2N ），其中x 0 ≤x 一≤x 2N 和X 0 ≤x B ≤x 2N 。从溶液中取出那些对，并且在他们的地方放（X 0 ，X 2N ）和（x 一，X 乙）。难道任一双新的presence已经损坏的解决方案？的对（x 0 中，x 2n个）不能有，因为它的总和小于或等于的和（x B ， x 2n个），它是原始的，最优解的成员。无论是再能（X 一，X B ）造成损害，因为它的总和小于或等于的总和（X B ，X 2N ），这是同一个解决方案中的一员。我们已经构建了的的最佳解决方案确实的包含（X 0 ，X 2N ）。

Consider any optimal solution which does not contain (x0, x2n). It must contain pairs (x0, xa) and (xb, x2n) with x0 ≤ xa ≤ x2n and x0 ≤ xb ≤ x2n. Remove those pairs from the solution, and in their place put (x0, x2n) and (xa, xb). Could the presence of either new pair have "damaged" the solution? The pair (x0, x2n) could not have, since its sum is less than or equal to the sum of (xb, x2n) which was a member of the original, optimal solution. Neither again could (xa, xb) have caused damage, since its sum is less than or equal to the sum of (xb, x2n), which was a member of the same solution. We have constructed an optimal solution which does contain (x0, x2n).

因此​​你给从未算法对其关闭发现在任何步骤的最佳解决方案的可能性，并且当存在仅仅两个值向左配对必须将它们一起配对

Thus the algorithm you give never forecloses the possibility of finding an optimal solution at any step, and when there are only two values left to pair they must be paired together.