Alpha Beta Gamma wants to make every office in the company look attractive. Interior decorators arc going to inspect every office. For cach office, they will decide how much cmpty space cach shelf with books can have. It is the same value for every shelf in that office. It is an upper bound, so Any book can be on any shelf. Every shelf in an office is the shelves may have less empty space. same size. The books start on the shelves, so you know that they fit. The interior decorators will check if it is feasible to place the books on the shelves to meet their goal. If it is not feasible, they will continuc to make the employce discard books, until their goal can be met. At that point, they will want the books shelved so that the maximum empty space is as small as possible. There are two problems that need to be solved. In both problems there are n books with widths , wn, where each width is a positive integer; and enough shelves to fit the books, where each shelf has integer width s space on any one shelf (being used) is at most g? shelf (being used) is as small as possible? (1) Given a goal g, is there a way to place the books on the shelves so that the maximum empty (2) How do you place the books on the shelves so that the maximum empty space on any one These two problems seem to be hard to solve efficiently. Not surprisingly, your manager asks you to write programs to solve the two problems. As usual you have no idea how to write such programs. For cach problem, you find an efficient program on the Internet that solves that problem Unfortunately your budget will only allow you to buy one such program 15. Assume that you have a program that solves the second problem in time ?(nr), for r > 1 Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm? Alpha Beta Gamma wants to make every office in the company look attractive. Interior decorators arc going to inspect every office. For cach office, they will decide how much cmpty space cach shelf with books can have. It is the same value for every shelf in that office. It is an upper bound, so Any book can be on any shelf. Every shelf in an office is the shelves may have less empty space. same size. The books start on the shelves, so you know that they fit. The interior decorators will check if it is feasible to place the books on the shelves to meet their goal. If it is not feasible, they will continuc to make the employce discard books, until their goal can be met. At that point, they will want the books shelved so that the maximum empty space is as small as possible. There are two problems that need to be solved. In both problems there are n books with widths , wn, where each width is a positive integer; and enough shelves to fit the books, where each shelf has integer width s space on any one shelf (being used) is at most g? shelf (being used) is as small as possible? (1) Given a goal g, is there a way to place the books on the shelves so that the maximum empty (2) How do you place the books on the shelves so that the maximum empty space on any one These two problems seem to be hard to solve efficiently. Not surprisingly, your manager asks you to write programs to solve the two problems. As usual you have no idea how to write such programs. For cach problem, you find an efficient program on the Internet that solves that problem Unfortunately your budget will only allow you to buy one such program 15. Assume that you have a program that solves the second problem in time ?(nr), for r > 1 Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm
