Question

IMPORTANT: Please write your answer inside the box that follows each question. Question 1 (4 points) Consider the following "greedy" strategy for the rod cutting problem: define the density of a rod of length i to be p/i, that is, its value per inch. The greedy strategy for a rod of lengt applying the greedy strategy to the remaining piece of length n - i. h n cuts off a first piece of length i, which has the maximum density. It then continues by a) Fill out the density values in the following table Length i (inch)2 34 1 58910 2.67 5 Price Pi (dollar) 1 8 Density pi/i b) According to the greedy strategy, if we are to cut a rod of length 5, what is the length of the first picce to cut off? What is the resulting revenue of the greedy solution? Is this the maximum revenue amongst all possible ways of cut? Hint: You can represent a way of cut by summation expression, e.g., 5-1+2+2, etc. c) If we are to cut a rod of length 4, what is the solution given by the greedy strategy? (represent it with a summation expression). Does it give the maximum revenue? If not, what is optimal way to cut?

Answer 1

2,62

If you have any query then feel free to ask in comment.