最小化排列和的贪心算法
Greedy algorithm to minimize the sum of a permutation
我有一个数组 {a1,a2,....,an}（自然数），我需要构建一个贪心算法来找到 1....n 的排列 (i1,...in)，使总和最小化: 1.ai1 + 2.ai2 + .... + (n − 1)ain−1 + n.ain.
当然我可以尝试所有这些，select 给出最小和的那个（这将在 O(n!) 中给出正确的结果）。
虽然我贪婪的选择是按降序选择数字，但我不知道如何证明这是有效的。
P.S：学习训练，不能“贪心”思考
按降序选择数字是最优的。
通过对 n 的归纳法证明：假设有一个最优排列，并且最小的数字不在最后一位。然后，交换最后位置的元素和最小的元素减少总和。这与最优性假设相矛盾，所以我们必须让最小的元素排在最后。根据归纳假设，其他元素在前（n-1）位递减。
n=1 的基本情况很简单。
我有一个数组 {a1,a2,....,an}（自然数），我需要构建一个贪心算法来找到 1....n 的排列 (i1,...in)，使总和最小化: 1.ai1 + 2.ai2 + .... + (n − 1)ain−1 + n.ain.
当然我可以尝试所有这些，select 给出最小和的那个（这将在 O(n!) 中给出正确的结果）。
虽然我贪婪的选择是按降序选择数字，但我不知道如何证明这是有效的。
P.S：学习训练，不能“贪心”思考
按降序选择数字是最优的。
通过对 n 的归纳法证明：假设有一个最优排列，并且最小的数字不在最后一位。然后，交换最后位置的元素和最小的元素减少总和。这与最优性假设相矛盾，所以我们必须让最小的元素排在最后。根据归纳假设，其他元素在前（n-1）位递减。
n=1 的基本情况很简单。