question archive A long rod of length m needs to be cut into pieces
Subject:Computer SciencePrice: Bought3
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, {C1,...,Cn}, 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 i2, 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 c1 = 4 and c2 = 8:
Making cut 2 and then cut 1 will cost 102 + 82 = 164
Making cut 1 and then cut 2 will cost 102 + 62 = 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 {c1,...,¢n} in ascending order, find an order in which to make the cuts that will minimize the cost.