1. This problem is called the Rod-Cutting Problem. The formulation of the problem is as follows: Given a rod of length n inches and a table of prices p; for i = 1, 2,..., n, determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces. Note that if the price pn for a rod of length n is large enough, an optimal solution may require no cutting at all. a) Formulate this problem using sub problems. b) Analyse the sub-problems and comment on whether the sub-sub-problems of those sub-problems overlap or not. length, i 1 2 3 4 5 6 7 8 9 10 price, Pi 1 5 8 10 14 8 9 7 4 13 Table 1: Length and associated price for an instance of a rod cutting problem c) For the instance of the rod-cutting problem given in Table 1, can you find an optimal solution? Build a dynamic-programming table and analyse that table to find the optimal solution. You can write necessary code to build the table. Include the table in your report. d) Does the following greedy strategy work for the instance of the rod-cutting problem given in Table 12 Define the density of a rod of length i to be pi/1, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1 sin, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n