Write a dynamic programming code for the Rod Cutting problem. Use the prices given to test your program:

 

• Given the prices p(i) of rods with length i = 1,2, .., n. We want to find the best cutting strategy of a rod with length l < n that maximizes the revenue. • Recurrence formula : r(l) = max (p(i) + r(l –i)) for 1 < i < n; r(0) = 0 • We can have two algorithms: 1. Recursive; rRodCut(p, l) 

2. Tabular or Dynamic Programming; dpRodCut(p, l) rRodCut(p, l) in matlab function r= RodCut(p,l) if l == 0 r=0; end q = -inf; for i = 1:l q=max(q,p(i)+RodCut(p,l-i)); r=q; end  >> p=[1,5,8,9,10,17,17,20,24,30] p = 1 5 8 9 10 17 17 20 24 30 >> for i=1 : 10 r(i)=RodCut(p,i);end >> r r = 1 5 8 10 13 17 18 22 25 30