Question

Rod cutting. Recall the rod cutting problem we learned (ch 15). In the problem, we're given a rod of length n along with an array {p_1}i lessthanorequalto i lessthanorequalto n- in which jh denotes the price you can charge for a rod/piece of length i. The goal is to cut the given rod of length n into smaller pieces (or do nothing) so that the total price of the pieces is maximized. Fill out the following table using the recursion in the textbook. Here r_i denotes the max revenue you can get out of a rod of length i. No need to explain your results.

Answer 1

Length i	1	2	3	4	5	6	7	8
Price pi	1	3	7	4	9	13	15	16
Cutting of the rod (new lengths)	1	2	3	1+3	2+3	3+3	7	3+3+2
Total maximum price	1	3	7	8	10	14	15	17