Part 111 adapted from "Algorithms" by Dasgupta, Papadimitriou and Vazirani). (20 pts): [This is like a 2-dimensional version of the rod-cutting problem] Cutting cloth. You are given a rectangular piece of cloth with dimensions W x H where W and Hare positive integers. You also have a list of n rectangular dimensions Wi, h; for which there is market demand; for each such dimension, you also have a price Pi: {(W1, h, P), (w2, h2, P2), ..., (Wn, hn, Pn)} All values are positive integers. For example, an entry of (2,3,4) indicates that you can sell a 2-by-3 piece of cloth for 4 dollars. You have a machine which can cut any rectangular piece of cloth into two pieces either horizontally or vertically -- i.e., you must cut all the way through! Design an algorithm which determines the best return on the W x H cloth -- i.e., a strategy for cutting the cloth so that the sale of the resulting pieces maximizes revenue. You are free to make as many copies of any particular rectangle size as you like (or none). Also, note that pieces of cloth can always be rotated -- e.g., a 3x4 piece of cloth is the same as a 4x3 piece of cloth. For simplicity, you may assume that redundant entries are included in your list of selling prices; for instance, if a 3x4 piece of cloth sells for $2.00, you can assume there is a symmetric entry of a 4x3 piece of cloth selling also for $2.00. Your algorithm must be polynomial in W, H and n. Give a runtime analysis of your algorithm. Part 111 adapted from "Algorithms" by Dasgupta, Papadimitriou and Vazirani). (20 pts): [This is like a 2-dimensional version of the rod-cutting problem] Cutting cloth. You are given a rectangular piece of cloth with dimensions W x H where W and Hare positive integers. You also have a list of n rectangular dimensions Wi, h; for which there is market demand; for each such dimension, you also have a price Pi: {(W1, h, P), (w2, h2, P2), ..., (Wn, hn, Pn)} All values are positive integers. For example, an entry of (2,3,4) indicates that you can sell a 2-by-3 piece of cloth for 4 dollars. You have a machine which can cut any rectangular piece of cloth into two pieces either horizontally or vertically -- i.e., you must cut all the way through! Design an algorithm which determines the best return on the W x H cloth -- i.e., a strategy for cutting the cloth so that the sale of the resulting pieces maximizes revenue. You are free to make as many copies of any particular rectangle size as you like (or none). Also, note that pieces of cloth can always be rotated -- e.g., a 3x4 piece of cloth is the same as a 4x3 piece of cloth. For simplicity, you may assume that redundant entries are included in your list of selling prices; for instance, if a 3x4 piece of cloth sells for $2.00, you can assume there is a symmetric entry of a 4x3 piece of cloth selling also for $2.00. Your algorithm must be polynomial in W, H and n. Give a runtime analysis of your algorithm
