What is the best algorithm for this?
We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at a time. The cost of each addition is the sum of the two integers, and this sum adds up cumulatively. After each addition, the two integers are removed from the array, but their sum is added, until only one value remains.
I think I have figured out so far that the optimal solution is to add up the two smallest values in the array at every step (as the earlier the figure is used the more times it is included in the cumulative cost.) Perhaps there is another way to think about the problem, though.
Is there some mathematical fact that trivializes the solution perhaps?
Example A:
Input: [1, 5, 3, 7]
Adding 1 and 3 together (Cost 1+3 = 4)
State: [5, 7, 4]
Adding 4 and 5 together (Cost 4+5 = 9)
State: [7, 9]
Adding 7 and 9 together (Cost 7+9 = 16)
State: [16]
Total cost: 4 + 9 + 16 = 29
Example B:
Input: [1, 1, 1, 1, 1]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 1, 1, 2]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 2, 2]
Adding 1 and 2 together (Cost 1+2 = 3)
State: [2, 3]
Adding 2 and 3 together (Cost 2+3 = 5)
State: [5]
Total cost: 2 + 2 + 3 + 5 = 12
(I made these examples up myself; let me know if the examples are not actually the optimal solutions, although I am pretty confident they are.)