5. (Advanced) Limited-Rod-Cutting. Let's consider another variant of the rod-cutting problem. The input is exactly the...

 

Transcribed Image Text:

5. (Advanced) Limited-Rod-Cutting. Let's consider another variant of the rod-cutting problem. The input is exactly the same, P1, P2, Pn. The only difference is that we're allowed to make at most 10 cuts. In other words, you want to maximize your revenue by cutting a rod of length n into at most 11 pieces. Our goal is to give a O(n) time algorithm for this task. As before, let's focus on computing the optimum. (a) Give a simple O(n0) time algorithm. (b) We need to extend subproblems. Let rik denote the max revenue you can get from a rod of length i by making at most k cuts. We will be interested in computing Tn,10- Give a recurrence for computing rik (c) Give a DP. You can simply state how the DP table is defined, and in which order you will compute the DP entries. What is the number of DP entries? How much time do you need to compute each entry? What is the running time of your dp? (d) In the above, we only computed rn,10. How do you find a solution that gives the revenue? 5. (Advanced) Limited-Rod-Cutting. Let's consider another variant of the rod-cutting problem. The input is exactly the same, P1, P2, Pn. The only difference is that we're allowed to make at most 10 cuts. In other words, you want to maximize your revenue by cutting a rod of length n into at most 11 pieces. Our goal is to give a O(n) time algorithm for this task. As before, let's focus on computing the optimum. (a) Give a simple O(n0) time algorithm. (b) We need to extend subproblems. Let rik denote the max revenue you can get from a rod of length i by making at most k cuts. We will be interested in computing Tn,10- Give a recurrence for computing rik (c) Give a DP. You can simply state how the DP table is defined, and in which order you will compute the DP entries. What is the number of DP entries? How much time do you need to compute each entry? What is the running time of your dp? (d) In the above, we only computed rn,10. How do you find a solution that gives the revenue?