Every year, Professor Dumbledore assigns the instructors at Hogwarts to various faculty committees.
There are n faculty members and c committees. Each committee member has submitted a list of
their prices for serving on each committee; each price could be positive, negative, zero, or even
infinite. For example, Professor Snape might declare that he would serve on the Student Recruiting
Committee for 1000 Galleons, that he would pay 10000 Galleons to serve on the Defense Against
the Dark Arts Course Revision Committee, and that he would not serve on the Muggle Relations
committee for any price.
Conversely, Dumbledore knows how many instructors are needed for each committee, as
well as a list of instructors who would be suitable members for each committee. (For example:
"Dark Arts Revision: 5 members, anyone but Snape.") If Dumbledore assigns an instructor to a
committee, he must pay that instructor’s price from the Hogwarts treasury.
Dumbledore needs to assign instructors to committees so that (1) each committee is full, (3) no
instructor is assigned to more than three committees, (2) only suitable and willing instructors
are assigned to each committee, and (4) the total cost of the assignment is as small as possible.
Describe and analyze an efficient algorithm that either solves Dumbledore’s problem, or correctly
reports that there is no valid assignment whose total cost is finite