Suppose that in the rod-cutting problem, we also had limit l_i on the maximum number of pieces of length i we are allowed to produce, for i=1,2,...,n. Write a dynamic program for this modified problem.

Recursive top-down implementation The following procedure implements the computation implicit in equation (15.2) in a straightforward, top-down, recursive manner. CUT-ROD(p, n) 1 if n return 0 3 4 for 1 to n 5 max (q, plij CUT-RoD(p, n i)) 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 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 induction on n proves that this answer is equal to the desired answer rn, using equation (15.2) If you were to code up T-ROD in 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 For n 40, you would find that your program takes at least several minutes, and most likely more than an hour. I 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 4: 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 j 0,1 ...,n -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 TOn) 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, T (0) l and