Cutting a stick such that cost is minimized

Question

You have to cut a stick with length l into several pieces. Pieces are required to have lengths a1, ..., an, where ai is an integer. The cost of a cut is equal to the length of the stick on which it is made. Design an algorithm which finds smallest possible price of such cutting to n pieces. For example, consider a stick of length 15 and required pieces lengths 1, 2, 3, 4, 5. You could cut the sticks in the order given. The first cut would cost 15, since the stick is of length 15. The second cut would cost 14, since the remaining stick on which the cut is made is of length 15 - 1 = 14. The third cut would cost 12, since the length of the remaining stick is 14 - 2 = 12. The last cut would cost 9, since the length of the remaining stick is 12 - 3 = 4 + 5 = 9. The total cost is 15 + 14 + 12 + 9 = 50.

But if we do the cuts in better order for example cut first the length 9 to get the lengths 4 and 5 with second cut. Or if we cut the length 8 with first cut to get the lengths 3 + 5 in second cut we could find out that the minimal cost of cutting to all 5 pieces is 33.

Design an algorithm to find minimal price.

This question is similar to question: Optimally cutting a stick at specified locations

But note that the order sticks doesn't matter for me.

The algorithm should work for quite high n such as 500000. So any solution enumerating all subsets is bad for me.

The first thing which came to my mind was to split the input to two subsets of approximately same sums. But I believe this is NP hard problem and am not sure that it would allow me to find optimal solution to this problem anyway.

Answer 1

I don't have a proof that this is optimal, but I suspect that it is.

put your sticks into a priority queue
while len(queue) > 1:
    take 2 smallest sticks out of queue
    merge them (record the cost)
    put the merged stick back in the queue

In your example it comes up with combining 1, 2. Then combining (1,2), 3. Then combining 4, 5. Then combining (4,5), (1,2,3) for a total cost of 33. Reversing it we cut at 8 then 4 then 11 then 9.

UPDATE: With @greybeard's comment that this looks like Huffman, I recognize that this is trivially reduces to that, and I accidentally implemented Huffman coding here so this solution is correct. :-)

Now I need to read the proof that Huffman coding is optimal to refresh my memory...

Answer 2

I think you should minimize the cost of the next cut. A good way to do this is getting rid of bigger pieces faster. So first we can go with the total cut size which is the total, and subsequently, remove bigger pieces.

def get_min_costs_sorted(stick, pieces):
    if len(pieces) == 1:
        return 0
    piece = pieces[0]
    print("Cutting {} into {}-{}".format(stick, piece, stick - piece))
    return stick + get_min_costs_sorted(stick - piece, pieces[1:])

def get_min_costs(stick, pieces):
    pieces.sort(reverse=True)
    total = sum(pieces)
    if stick > total:
        print("Cutting {} into {}-{}".format(stick, total, stick - total))
        return stick + get_min_costs_sorted(total, pieces)
    else: # no cutting
        return get_min_costs_sorted(total, pieces)