分割2n个实数的序列,以便

Question

我正在阅读算法设计手册,我坚持这个练习.

---

取一系列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,这是三个分区的最小值.

---

我从一些例子中猜到,解决方案看起来像这样:

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

但如何证明呢？

Answer 1

算法有效,因为当x ₀,x ₁,... x _2n-1是排序列表时,总会有一个包含(x ₀,x _2n-1)的最优解.

证明:

考虑任何不包含(x ₀,x _2n-1)的最优解.它必须包含对(X ₀,X _一)和(x _b,X _2N-1 ),其中x ₀ ≤X _一 ≤X _2N-1 ,并且x ₀ ≤X _b ≤X _2N-1 .从解决方案中删除这些对,并在它们的位置放置(x ₀,x _2n-1)和(x _a,x _b).两个新对的存在是否"破坏"了解决方案？该对(x ₀,x _2n-1)不能具有,因为其总和小于或等于(x _b,x _2n-1)的总和,其是原始最优解的成员.(x _a,x _b)也不会造成损害,因为它的总和小于或等于(x _b,x _2n-1)的总和,它是同一解决方案的成员.我们已经构建了最佳的解决方案,其不包含(X ₀,X _2N-1 ).

因此,您提供的算法永远不会排除在任何步骤找到最佳解决方案的可能性,并且当只剩下两个值进行配对时,它们必须配对在一起.