Help with 15.1-3 only please! Recursive top-down implementation The following pr
ID: 3799865 • Letter: H
Question
Help with 15.1-3 only please!
Recursive top-down implementation The following procedure implements the com on implicit in equation (15.2) in a straightforward, top-down, recursive manner. CUT-RoD(p,n) 1 if n return 0 3 4 for to n max (a, plil CUT-RoD(p, 6 return Procedure CUT-RoD takes as input an array pl1..nl of prices and an integer n and it returns the maximum revenue possible for a rod of length n. If n 0, no revenue is possible, and so CUT-ROD returns 0 in line 2. Line 3 initializes the maximum revenue q to -oo, so that the for loop in lines 4 5 correctly computes maxi Sisn (pi +CUT-RoD(p, n -i)); line 6 then returns this value. A simple nduction on n proves that this answer is equal to the desired answer r, using equation (15.2). If you were to code upCUT-RoDin your favorite programming language and run it on your computer, you would find that once the input size becomes moderately large, your program would take a long time to run. Forn 40, you would find that your program takes at least several minutes, and most likely more than an hour. In fact, you would find that each time you increase n by 1 your program's running time would approximately double Why is CUT-ROD so inefficient? The problem is that CUT ROD calls itself recursively over and over again with the same parameter values, it solves the same subproblems repeatedly. Figure 15.3 illustrates what happens for n CUT-RoD(p,n) calls CUT-RoD(p,n i) for i 1,2 n. Equivalently, CUT-RoD(p, n) calls CUT-RoD(p, j) for each 0,1 When this process unfolds recursively, the amount of work done, as a function of n, grows explosively. To analyze the running time of CuT-RoD, let T(n) denote the total number of calls made to CUT-ROD when called with its second parameter equal to n. This expression equals the number of nodes in a subtree whose root is labeled n in the recursion tree. The count includes the initial call at its root. Thus, TO) 31 andExplanation / Answer
Consider a modification of the rod-cutting problem in which, in addition to a price pi for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.
MODIFIEDCUTROD (p, n, c)
Let r [0..n] to be new array
r[0] = 0
for j = 1 to n
q = p [ j ]
for I = 1 to j - 1
q = max (q, p [i]+ r [ j - i ] – c)
r[j] = q
return r[n]
The major modification required is in the body of the inner for loop, which now reads q = max(q, p[i] + r[j i] c). This change reflects the fixed cost of making the cut, which is deducted from the revenue. We also have to handle the case in which we make no cuts (when i equals j); the total revenue in this case is simply p[j]. Thus, we modify the inner for loop to run from i to j 1 instead of to j. The assignment q = p[j] takes care of the case of no cuts. If we did not make these modifications, then even in the case of no cuts, we would be deducting c from the total revenue.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.