最小化排列之和的贪心算法

Question

我有一个数组{a1,a2,....,an} (由自然数组成)，我需要构建一个贪婪的算法来找到一个排列(i1，...in)为1..n，从而最小化和：1.ai1 + 2.ai2 + .... + (n − 1)ain−1 + n.ain。

当然，我可以尝试所有的方法，并选择给出最小和的一个(这将给出O(n！)的正确结果)。

我认为贪婪的选择是按降序选择数字，但我不知道如何证明这是有效的。

附言:这只是为了学习和训练，我不能“贪婪”地思考。

Answer 1

按降序选择数字是最优的。

证据是通过对n的归纳来证明的:假设有一个最优的排列，最小的数字不在最后。然后，交换最后一个位置的元素和最小的元素会减少总和。这与最优性的假设相矛盾，所以我们必须确保最小的元素在最后。根据归纳假设，其他元素在前(n-1)位按降序排列。

n=1的基本情况很简单。