Question

The rod-cutting problem exhibits optimal substructure - that is, the optimal solution to maximizing revenue for cutting a rod of length n incorporates the optimal solution to some subproblems of cutting a rod of length less than n. (note that this allows the possibility that the optimal solution may not involve cutting the rod at all).
a. True
b. False

Answer 1

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 :

$r_{i} =max p_{n} , r_{1} , r_{n-1} , r_{2} , r_{n-2} + r_{1}$

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$