(10 points) In the rod cutting problem, we are given as input, P1.P2, Pn, where pi...

 

Transcribed Image Text:

(10 points) In the rod cutting problem, we are given as input, P1.P2, Pn, where pi denotes the price of a rod/piece of length i. We are interested in cutting a given rod of length n into pieces of integer lengths in order to maximize the revenue; here we are only interested in finding the maximum revenue. Cutting is free. Let r, denote the maximum revenue one can get out of a rod of length i. To solve the problem using DP (dynamic programming), we can use the following recursion: [maxicisi (P + r-) ifj21 to But Dr. Sponge thinks that perhaps he has a more efficient recursion and proposes the following: Tj Tj = otherwise (0) [max (pj, maxisist/2j(r +rj-)} ifj2 PI otherwise (j= 1) Does this proposed recursion correctly compute rj? Answer Yes or No, and explain why. (10 points) In the rod cutting problem, we are given as input, P1.P2, Pn, where pi denotes the price of a rod/piece of length i. We are interested in cutting a given rod of length n into pieces of integer lengths in order to maximize the revenue; here we are only interested in finding the maximum revenue. Cutting is free. Let r, denote the maximum revenue one can get out of a rod of length i. To solve the problem using DP (dynamic programming), we can use the following recursion: [maxicisi (P + r-) ifj21 to But Dr. Sponge thinks that perhaps he has a more efficient recursion and proposes the following: Tj Tj = otherwise (0) [max (pj, maxisist/2j(r +rj-)} ifj2 PI otherwise (j= 1) Does this proposed recursion correctly compute rj? Answer Yes or No, and explain why.

Answer rating: 100% (QA)

DP solution Rj MaxPiRji for 1 Ri Rji Pi Rj... View the full answer