Give a decision problem corresponding to each of the search problems given below. (a) • Input: A set of classes to be scheduled. A list of pairs of the classes which can not be scheduled during the same period.
• Output: The largest set of classes that can all be scheduled during the same period.
Solution
• Input: A set of classes to be scheduled. A list of pairs of the classes which can not be scheduled during the same period. An integer k.
• Output: "Yes" if there is a set of k classes that can be all scheduled during the same period. "No" if there is no set of k classes that can all be scheduled at the same time.
b) • Input: A set of classes to be scheduled. A list of pairs of the classes which can not be scheduled during the same period.
• Output: A schedule for the classes that uses the smallest number of periods.
c) • Input: A list of items, each with a value and a weight. The values and weights of the items are positive integers. A positive integer W.
• Output: A subset of the items whose total weight is at most W and whose total value is as large as possible.
Solution
• Input: A list of items, each with a value and a weight. The values and weights of the items are positive integers. A positive integer W. A positive integer V.
• Output: "Yes" if there is a subset of the items whose total value is at least V and whose total weight is at most W. Output "No", otherwise.