Write a function using Recursion to do the following: You are the manager in a small factory. You have 7 workers and 7 jobs to be done. Each worker is assigned one and only one job. Each worker demands different pay for each job. (E.g.: Worker Archie demands $10 for welding, $15 for carpentry, etc. Worker Jughead demands $12 for welding, $5 for carpentry, etc.) Find the job-assignment which works out cheapest for you.
-
-
Have you tried doing it? Post where exactly you are having trouble. No one will write the code for you. -
Hi Nithiya Kalyani,
Welcome to TSDN
Please make sure you follow POSTING GUIDELINES when ever you post in this forum.
MODERATORComment
-
Please post the following,Originally posted by Nithya Kalyani
1. Where is the data actually stored? Which databse you are using to store this data?
2. Is it mandatory to write a recursive function for this?
3. What you have tried to achieve this?Comment
-
Draw a 7x7 grid; the columns represent the workers, the rows represent the jobs.
The individual cells c_ij represent the cost when job i is done by worker j.
You have to mark one cell per column and per row such that the sum of the marked
c_ij is minimal.
Let a_ij in [0, 1] be an integer variable such that a_ij == 1 when job j is performed
by worker j, and 0 otherwise. So you have to minimize the following formula:
sum(i, j in [1, 7] | a_ij*c_ij). w.r.t. the constraints:
sum(i in [1, 7] | a_ij == 7) and
sum(j in [1, 7] | a_ij == 7).
This indeed is the classical "job assignment problem" which happens to be the
smallest class of problems in the MNCF ("Minimal Cost Network Flow") problems
and can be easily solved with a network simplex algorithm.
Solving it recursively is ludirous because it can be highly inefficient. The brutest
force method of them all is to iterate over the 7! possibilities and pick the cheapest.
kind regards,
JosComment
Comment