By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,238 Members | 1,182 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,238 IT Pros & Developers. It's quick & easy.

Write a function using Recursion to do the following

P: 2
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.
Nov 23 '07 #1
Share this Question
Share on Google+
4 Replies


P: 93
Have you tried doing it? Post where exactly you are having trouble. No one will write the code for you.
Nov 23 '07 #2

amitpatel66
Expert 100+
P: 2,367
Hi Nithiya Kalyani,

Welcome to TSDN

Please make sure you follow POSTING GUIDELINES when ever you post in this forum.

MODERATOR
Nov 23 '07 #3

amitpatel66
Expert 100+
P: 2,367
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.
Please post the following,

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?
Nov 23 '07 #4

Expert 10K+
P: 11,448
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,

Jos
Nov 23 '07 #5

Post your reply

Sign in to post your reply or Sign up for a free account.