V. (15 points) Serling Enterprises buys long steel rods and cuts them into shorter rods, which it then sells. Each cut i

[answerhappygod]

V 15 Points Serling Enterprises Buys Long Steel Rods And Cuts Them Into Shorter Rods Which It Then Sells Each Cut I 1 (58.12 KiB) Viewed 25 times

V. (15 points) Serling Enterprises buys long steel rods and cuts them into shorter rods, which it then sells. Each cut is free. The management of Serling Enterprises wants to know the best way to cut up the rods. We assume that we know, for i=1,2,... the price p, in dollars that Serling Enterprises charges for a rod of length i inches. (That is, assume that we are given an array P[1..n], where P = p, is the price of a rod of length i inches.) Rod lengths are always integral numbers. The rod-cutting problem is the following. Given a rod of length n inches and the prices p., for i = 1,..., n, determine the maximum revenue obtainable by cutting up the rod and selling the pieces. Note that if the price pn for a rod of length n is large enough, an optimal solution may require no cutting at all. (i) (5 points) Show that a greedy algorithm that always chooses to cut a piece with the maximum revenue may not be optimal. (ii) (5 points) Give a recursive definition of the maximum revenue obtainable for cutting a rod of length i inches. (Hint. A cutting of a rod of length i inches into pieces can be expressed as: cutting a single piece, plus a cutting of the remaining portion of the rod into pieces.) (iii) (5 points) Use part (ii) above to give an O(n²)-time dynamic programming algorithm for solving the rod-cutting problem.