如何证明该算法的正确性？

Question

一家家具店正在打折:以更贵的价格购买两件物品。约翰刚搬到一个新房子，冲进商店，选择了2k家具: f1，f2，…，f2k−1，f2k。价格分别为p1、p2、.、p2k−1、p2k。帮助约翰安排家具成对，这样2k项目的总成本是最低的。提出了一种在O(klogk)中运行的算法，证明了算法的正确性和运行时间。

好的，听起来并不复杂:首先，我将按价格对所有2k家具进行排序，然后每个单元格和他的下一个单元格是一个couple.takes O(klogk)。

我怎样才能证明我的建议是正确的？我想假设有更小的解决方案，并得到一个矛盾，但我不知道如何证明这一点。很多次！

Answer 1

你想买2k件家具，每件都是一副。现在让我们按价格的递减顺序来考虑这些产品。最昂贵的一件需要一对，因为它是最昂贵的，它将比另一件更昂贵的一对。因此，你可以免费购买任何一件家具。让我们假设最好的解决方案组是价格为X的最昂贵的部分，我们进一步假设这个部分在价格上不是第二个(让我们表示第二个价格片段S)。现在，S是它自己的一对，这对的价格不可能比S的价格高。现在，如果我们改变S和X的位置，所有对的价格都会改变，但是X过去的位置和S过去的价格将保持不变。由于S现在是具有最昂贵元素的组，这对的价格也保持不变。对于X现在是的对，它不可能增加，因为这意味着X比S更昂贵，这是一个矛盾。

因此，新的解也是最优的，因此，总是有一个解，其中最昂贵的元素与第二到最后的分组。现在，您可以使用归纳来证明您的方法的正确性。