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.

Answer rating: 100% (QA)

Greedy Algorithm for Rod Cutting The greedy algorithm for the rod cutting problem is quite simple It tries to maximize the value at each step by choos... View the full answer