Given a rod of length n inches and an array of prices (pi, for i = 1...n) of all pieces of size smaller than or equal to n, that is pi is the price for a piece of length i inches. The Rod Cutting problem is to determine the maximum value obtainable by cutting up the rod and selling the pieces.
a) Describe a greedy algorithm to determine a set of piece sizes to cut up a rod to maximize the value when selling the pieces. For example, given p = [1, 3, 4, 5], the optimal solution would be [2, 2]. That is, a 4- inch rod is divided into two 2-inch pieces worth 3 each, for a total of
6.a) Give a set of prices for which the greedy algorithm does not yield an optimal solution. Show the solution your algorithm yields along with an optimal solution.