1. A long rod of length m needs to be cut into pieces. You already have...

Transcribed Image Text:

1. 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₁, ..., 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 C₁ = 4 and c₂ = 8: making cut 2 and then cut 1 will cost 10² +8² making cut 1 and then cut 2 will cost 10² +6² 136 164 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₁,..., Cn} in ascending order, find an order in which to make the cuts that will minimize the cost. 1. 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₁, ..., 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 C₁ = 4 and c₂ = 8: making cut 2 and then cut 1 will cost 10² +8² making cut 1 and then cut 2 will cost 10² +6² 136 164 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₁,..., Cn} in ascending order, find an order in which to make the cuts that will minimize the cost.

Answer rating: 100% (QA)

Here mlength of rod nno of points c1 upto cn cost oof poin... View the full answer