Sticks

October 7, 2016

We continue our occasional series of textbook exercises:

You are given a bunch of sticks, each of integer length. Two sticks can be combined into a single, larger stick by a process that costs the sum of the lengths of the two sticks. Your goal is to build a single stick combining all the original sticks, at minimal cost.

For example, suppose you initially have three sticks of lengths 1, 2, and 4. You could combine sticks 2 and 4 at a cost of 6, then combine that stick with stick 1 at a cost of 7, for a total cost of 13. But it is better to first combine sticks 1 and 2 at a cost of 3, then combine that stick with stick 4 at a cost of 7, for a total cost of 10.

Your task is to write a program that combines a bunch of sticks at minimal cost. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2