Respuesta :
Answer:
It is right to cut a rod into pieces to maximize revenue
when a rod is cut then rod lengths are an integral number of inches
Let's suppose length n and table of prices for i = 1,2,.......,n is given input and the maximum revenue for rods whose sum to n. If p is large, then the optimal solution requires no cuts.
Explanation:
Lets suppose possible cuts length and price
length i = 1 2 3 4 5 6 7 8 9 10
price p = 1 5 8 9 10 17 17 20 24 30
i r optimal solution
1 1 no cuts
2 5 no cuts
3 8 no cuts
4 10 2+2
5 13 2+3
6 17 no cuts
7 18 1+ 6
8 22 2+ 6
Optimal revenue in shorter rods :
[tex]r_{i} =max p_{n} , r_{1} , r_{n-1} , r_{2} , r_{n-2} + r_{1}[/tex]
After making a cut we have sub problems
For example, n= nine optimal solutions cut 2 inches; there are two sub problems of lengths two, and 7.there is a need to save both optimal. The optimal solution for the problem of length 2 is no cut and optimal solution for length seven is cut into length 5 and 2 then 2 is no cut then the optimal solution for length five is cut into length 2 and 3 then price will be 5$ + 5$ + 5$ + 8$ = 23$
