In the rod cutting example we discussed in class, given a rod of length n and a
Fantastic news! We've Found the answer you've been seeking!
Question:
recurrence: rn = max{pi + rn−i : 1 ≤i ≤n}.
Consider a variant of this problem where a fixed cost c is associated with making each cut, please answer the following questions. Thus, the revenue becomes the total prices of all cut rods minus the total costs associated with making the cuts.
(a) What is the recurrence for the new problem?
(b) Please provide pseudocode for a dynamic programming algorithm that uses the bottom-up method.
(c) Please provide pseudocode for a dynamic programming algorithm that uses the top-down with mem-oization approach.
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date: