Greedy algorithm to minimize the sum of a permutation

Question

I have an array {a1,a2,....,an} (of natural numbers), i need to build an greedy algorithm that finds a permutation (i1,...in) of 1....n that minimizes the sum: 1.ai1 + 2.ai2 + .... + (n − 1)ain−1 + n.ain.

Definitely I can just try all of them and select the one which gives the smallest sum (this will give correct result in O(n!)).

The greedy choice that i though is to choose the numbers in decreasing order, but i don't know how to prove that this works.

P.S: this is just for study and training, I'm not being able to think "greedly"

Answer 1

Choosing the numbers in decreasing order is optimal.

Proof is by induction on n: suppose there's a permutation that is optimal and that the smallest number is not in the last place. Then, swapping the element that is in the last place and the smallest element decreases the total sum. That contradicts the assumption of optimality, so we must have that the smallest element is in the last place. By the induction hypothesis, the other elements are in decreasing order in the first (n-1) places.

The base case of n=1 is trivial.