Problem 4. (10 points) A garment company sells n different garments, the th of which requires one rectangular piece of cloth which is a; inches long and b; inches wide, and sells for vi dollars. A large piece of cloth arrives on a roll of length L inches and width W inches. Assume that L, W, di, and b; are integers. The machine that cuts a large piece of cloth can only cut a rectangular piece of cloth horizontally or vertically into two (not necessarily equal) rectangular pieces that is, it can only cut all the way across from top to bottom or from left to right. You want to use this machine to cut up the L x W piece of cloth, so as to make a set of garments maximizing the total revenue in dollars. Note that you may make multiple copies of any one garment. As an example, you might cut a 4 x 5 cloth into 1 x 5 and 3 x 5, then cut the 1 x 5 into 1 x 2 and 1 x 3, and cut the 3 x 5 into 3 x 2 and 3 x 3. Then, you might cut the 3 x 3 into 3 x 2 and 3x1. At this point, you end up with one piece of 1 x 2, two pieces of 1 x 3, and two pieces of 2 x 3, which might be the final sizes you turn into actual garments. Give and analyze) an algorithm that computes the maximum revenue possible, in time poly- nomial in n, L, and W. It is enough for your algorithm to compute the maximum revenue - it does not need to output the actual rectangles. Note that length and width are interchangeable, i.e., a piece of cloth of length a and width b is identical to a piece of cloth of length b and width a. Problem 4. (10 points) A garment company sells n different garments, the th of which requires one rectangular piece of cloth which is a; inches long and b; inches wide, and sells for vi dollars. A large piece of cloth arrives on a roll of length L inches and width W inches. Assume that L, W, di, and b; are integers. The machine that cuts a large piece of cloth can only cut a rectangular piece of cloth horizontally or vertically into two (not necessarily equal) rectangular pieces that is, it can only cut all the way across from top to bottom or from left to right. You want to use this machine to cut up the L x W piece of cloth, so as to make a set of garments maximizing the total revenue in dollars. Note that you may make multiple copies of any one garment. As an example, you might cut a 4 x 5 cloth into 1 x 5 and 3 x 5, then cut the 1 x 5 into 1 x 2 and 1 x 3, and cut the 3 x 5 into 3 x 2 and 3 x 3. Then, you might cut the 3 x 3 into 3 x 2 and 3x1. At this point, you end up with one piece of 1 x 2, two pieces of 1 x 3, and two pieces of 2 x 3, which might be the final sizes you turn into actual garments. Give and analyze) an algorithm that computes the maximum revenue possible, in time poly- nomial in n, L, and W. It is enough for your algorithm to compute the maximum revenue - it does not need to output the actual rectangles. Note that length and width are interchangeable, i.e., a piece of cloth of length a and width b is identical to a piece of cloth of length b and width a