CODEWITHSUNDEEP
algorithmmathdata-structures
Sathya
Sathya

Reputation: 5308

Need an algorithm for below distribution

I need an algorithm for below problem.

I have teachers and each teacher has their preferred subject. For example,

Teacher 1 might have preferred science, maths and computers
Teacher 2 might have preferred english and maths
Teacher 3 might have preferred science, english and maths
like so.....

And i have N number of answer sheets. Each will fall under any one of the subject (english, science, maths and computers). I need to assign these answer sheets to each teacher based on their preference. But maximum we can assign 50 papers to a teacher. And if we have 1000 answer sheets, we'll have minimum 20 teachers (1000/50).

And if we have 112 answer sheets in maths and if we have two teachers with maths preference, we can assign 100 to them and the rest 12 we can assign to any teacher (which comes under non preferred category).

This algorithm's success will be determined by how efficiently it allocates answer sheets to teachers based on their preference and how much less they have non-preferred answer sheets.

Can anyone tell me which algorithm suits for it?

Upvotes: 1

Views: 122

Answers (1)

Ron Teller
Ron Teller

Reputation: 1890

This problem can be formulated as a simple assignment problem (assigning n jobs to n workers):

Each teacher appears 50 times as a worker, and each sheet appear once as a job.

A teacher is connected to a sheet with weight 0 if it's one of his preferred subjects, and weight 1 if not. If there are more workers (50 * number of teachers) than jobs, add fictive jobs (until the numbers of workers equal the number of jobs) that are connected to all the workers with weight 0, these jobs can be ignored in the solution.

From this point, refer to any algorithm that solves the assignment problem (see the wiki link). you want to find the assignment with the minimal weight.

Upvotes: 3

Related Questions