For the problem below, two ”high level” greedy strategy is given. One of the strategies gives a correct solutions, and the other sometimes gives an incorrect solutions. Decide which greedy strategy produces optimal solutions, and give a proof that it is correct and a counter-example showing the other strategy is incorrect.( show proof and counter example) You are given a list of classes C and a list of classrooms R. Each class c has a positive enrollment E(c) and each room r has a positive integer size S(r) which denotes its capacity. You want to assign each class a room in a way that minimizes the total sizes of rooms used. However, the capacity of the room assigned to a class must be at least the enrollment of the class. You cannot assign two classes to the same room. Greedy strategy A: Repeat until all classes are assigned, or a class cannot be included in any unassigned room. Assign the largest unassigned class to the smallest unassigned room larger than or equal to its enrollment. Greedy Strategy B: Repeat until all classes are assigned or a class cannot be included in any unassigned room: Assign the largest unassigned room to the largest unassigned class smaller than or equal to its capacity.
For the problem below, two ”high level” greedy strategy is given. One of the strategies gives
a correct solutions, and the other sometimes gives an incorrect solutions. Decide which greedy strategy
produces optimal solutions, and give a proof that it is correct and a counter-example showing the other
strategy is incorrect.( show proof and counter example)
You are given a list of classes C and a list of classrooms R. Each class c has a positive enrollment E(c)
and each room r has a positive integer size S(r) which denotes its capacity. You want to assign each
class a room in a way that minimizes the total sizes of rooms used. However, the capacity of the room
assigned to a class must be at least the enrollment of the class. You cannot assign two classes to the
same room.
Greedy strategy A: Repeat until all classes are assigned, or a class cannot be included in any unassigned
room. Assign the largest unassigned class to the smallest unassigned room larger than or equal to its
enrollment.
Greedy Strategy B: Repeat until all classes are assigned or a class cannot be included in any unassigned
room: Assign the largest unassigned room to the largest unassigned class smaller than or equal to its
capacity.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
