QUESTION 1- If you don't think enough is described here, the book is called Introduction to Algorithms, 3rd ed., Cormen, Leiserson, Rivest, and Stein. MIT Press. The example number is shown and can be found via search (15.1 and 15.3-5)

Question 2:

Consider the following modification of the rod-cutting problem: A given instance of RCP may have many different solutions with the same maximum revenue. Suppose we wanted to find a solution that yields maximum revenue with the least number of cuts. Design a dynamic program for this problem.

15.3-5 Suppose that in the rod-cutting problem of Section 15.1, we also had limit l on the number of pieces of length i that we are allowed to produce, for i 1,2.... .n Show that the optimal-substructure property described in Section 15.1 no longer holds. The rod-cutting problem is the following. Given a rod of length n inches and a table of able 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. prices p for i1,2.....n, determine the maximum revenue robtain- Consider the case when n = 4. Figure 15.2 shows all the ways to cut up a rod of 4 inches in length, including the way with no cuts at all. We see that cutting a 4-inch rod into two 2-inch pieces produces revenue P2 + P2 = 5 + 5 = 10, which is optimal. We can cut up a rod of length n in 2- different ways, since we have an in dependent option of cutting, or not cutting, at distance i inches from the left end, length 2 345 67 8 910 price p 5 8 9 10 17 17 20 24 30 More generally, we can frame the values rn for in terms of optimal rev The first argument, P, corresponds to making no cuts at all and selling the rod of length n as is. The other n - 1 arguments to max correspond to the maximum rev- enue obtained by making an initial cut of the rod into two pieces of size i andn -i for each i -1,2.... .n - 1, and then optimally cutting up those pieces further obtaining revenues r and rn-i from those two p of time which value ofi optimizes revenue, we have to consider all possible values for i and pick the one that maximizes revenue. We also have the option of picking no i at all if we can obtain more revenue by selling the rod uncut. 0 pieces. Since we don't know ahead Note that to solve the original problem of size n, we solve smaller problems of the same type, but of smaller sizes. Once we make the first cut, we may consider the two pieces as independent instances of the rod-cutting problem. The overall optimal solution incorporates optimal solutions to the two related subproblems, maximizing revenue from each of those two pieces. We say that the rod-cutting problem exhibits optimal substructure: optimal solutions to a problem incorporate optimal solutions to related subproblems, which we may solve independently 15.3-5 Suppose that in the rod-cutting problem of Section 15.1, we also had limit l on the number of pieces of length i that we are allowed to produce, for i 1,2.... .n Show that the optimal-substructure property described in Section 15.1 no longer holds. The rod-cutting problem is the following. Given a rod of length n inches and a table of able 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. prices p for i1,2.....n, determine the maximum revenue robtain- Consider the case when n = 4. Figure 15.2 shows all the ways to cut up a rod of 4 inches in length, including the way with no cuts at all. We see that cutting a 4-inch rod into two 2-inch pieces produces revenue P2 + P2 = 5 + 5 = 10, which is optimal. We can cut up a rod of length n in 2- different ways, since we have an in dependent option of cutting, or not cutting, at distance i inches from the left end, length 2 345 67 8 910 price p 5 8 9 10 17 17 20 24 30 More generally, we can frame the values rn for in terms of optimal rev The first argument, P, corresponds to making no cuts at all and selling the rod of length n as is. The other n - 1 arguments to max correspond to the maximum rev- enue obtained by making an initial cut of the rod into two pieces of size i andn -i for each i -1,2.... .n - 1, and then optimally cutting up those pieces further obtaining revenues r and rn-i from those two p of time which value ofi optimizes revenue, we have to consider all possible values for i and pick the one that maximizes revenue. We also have the option of picking no i at all if we can obtain more revenue by selling the rod uncut. 0 pieces. Since we don't know ahead Note that to solve the original problem of size n, we solve smaller problems of the same type, but of smaller sizes. Once we make the first cut, we may consider the two pieces as independent instances of the rod-cutting problem. The overall optimal solution incorporates optimal solutions to the two related subproblems, maximizing revenue from each of those two pieces. We say that the rod-cutting problem exhibits optimal substructure: optimal solutions to a problem incorporate optimal solutions to related subproblems, which we may solve independently