Suppose we have a rod of length n inches and we also have an array of...

 

Transcribed Image Text:

Suppose we have a rod of length n inches and we also have an array of prices P, where P[i] denotes the selling price ($) of a piece that is i inches long. (See CLRS Ch15.1 for reference, which gives an algorithm that uses dynamic programming to find a way of cutting the rod into pieces that maximizes the revenue). Suppose now we have to pay a cost of $1 per cut. Define the profit we make as the revenue minus the total cost of cutting. We want an algorithm that finds a way to cut the rod maximizing our profit. For your DP algorithm, use the name MAXPROFIT for the (potentially multi-dimensional) array which stores values of the subproblems. 1. What is the dimension of the array MAXPROFIT? 2. State the base cases and their values. 3. Give and justify the recurrence MAXPROFIT should satisfy. 4. Based on the recurrence, write pseudocode that computes MAXPROFIT and outputs the maximum profit for the given rod of length n. State and explain the run time of your algorithm as a big-> expression. Suppose we have a rod of length n inches and we also have an array of prices P, where P[i] denotes the selling price ($) of a piece that is i inches long. (See CLRS Ch15.1 for reference, which gives an algorithm that uses dynamic programming to find a way of cutting the rod into pieces that maximizes the revenue). Suppose now we have to pay a cost of $1 per cut. Define the profit we make as the revenue minus the total cost of cutting. We want an algorithm that finds a way to cut the rod maximizing our profit. For your DP algorithm, use the name MAXPROFIT for the (potentially multi-dimensional) array which stores values of the subproblems. 1. What is the dimension of the array MAXPROFIT? 2. State the base cases and their values. 3. Give and justify the recurrence MAXPROFIT should satisfy. 4. Based on the recurrence, write pseudocode that computes MAXPROFIT and outputs the maximum profit for the given rod of length n. State and explain the run time of your algorithm as a big-> expression.