449,238 Members | 1,182 Online
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
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

 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

 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