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.)

  • (Sounds Huffman rather than subset sum.) – greybeard Dec 5 at 6:17
  • @graybeard Thanks, I removed it. I was trying to look for something fitting containing "sum"... – MakaPeia Dec 5 at 18:05
up vote 0 down vote accepted

This problem can be solved using a min heap. You have to construct a min heap initially with all the elements of array. Now you simply take the top element of this heap and add it to the next top element of heap. Then reinsert the sum obtained in the heap. Keep a variable to track the total cost. This will ensure that you are adding the minimum elements and the final cost is minimum. This is analogous to the problem of connecting n ropes with minimum cost.

  • Wow! Thanks friend! I felt there would be a "simple" solution... The min heap algorithm is exactly what it needs. – MakaPeia Dec 5 at 18:04
  • I once tried this problem and came up with an algorithm which sorted the array and then kept on doing sum but that was incorrect. It missed some cases and min heap algorithm was the correct one. Reading your case it took me just a second to recognise the problem ;) – Navjot Waraich Dec 6 at 22:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.