Modified Rod Cutting Problem. Given n pieces of rod with lengths 11,12,...n Recursively combine two adjacent...

Transcribed Image Text:

Modified Rod Cutting Problem. Given n pieces of rod with lengths 11,12,...İn Recursively combine two adjacent pieces to have a rod of length n at the end. When combining the two pieces of length x and y, the revenue is actually x² + b². Write a dynamic programming algorithm that gives us the maximum revenue and explaining your running time. ex: given lengths n = 3: ₁ = $2, 12 = $1, 13 = $1 There are 2 ways to combine the pieces: (2+1) + 1: 2² x 1² = 4 4+9= $13 revenue then 3² x 1² = 9 -or- 2+(1+1): 12 x 1² = 1 then 2² x 2² = 16 1 + 16 = $17 revenue (correct answer max revenue of length(n) = 3) Modified Rod Cutting Problem. Given n pieces of rod with lengths 11,12,...İn Recursively combine two adjacent pieces to have a rod of length n at the end. When combining the two pieces of length x and y, the revenue is actually x² + b². Write a dynamic programming algorithm that gives us the maximum revenue and explaining your running time. ex: given lengths n = 3: ₁ = $2, 12 = $1, 13 = $1 There are 2 ways to combine the pieces: (2+1) + 1: 2² x 1² = 4 4+9= $13 revenue then 3² x 1² = 9 -or- 2+(1+1): 12 x 1² = 1 then 2² x 2² = 16 1 + 16 = $17 revenue (correct answer max revenue of length(n) = 3)

Answer rating: 100% (QA)

To solve the Modified Rod Cutting Problem using dynamic programming you can follow these steps 1 Cre... View the full answer