A long rod of length m needs to be cut into pieces

Subject:Computer SciencePrice: Bought3

Share With

A long rod of length m needs to be cut into pieces. You already have a list of the n points (distances from the start of the rod, all positive and distinct) where the cuts need to occur, {C₁,...,C_n}, and the rod has been marked accordingly.

The physical process of cutting the rod allows for the specified cuts to be made in any order, and as cuts are made you get a set of shorter rods (which may then be cut, if needed). The cost of cutting a rod of length i is i², irrespective of where the cut occurs, and we want to minimize the total cost of making the cuts.

For example, for m = 10, n = 2, with c₁ = 4 and c₂ = 8:

Making cut 2 and then cut 1 will cost 10² + 8² = 164

Making cut 1 and then cut 2 will cost 10² + 6² = 136

So the second order is cheaper.

Design and write, in pseudocode, a dynamic programming algorithm that will, given m, n, and the desired cut locations {c₁,...,¢_n} in ascending order, find an order in which to make the cuts that will minimize the cost.