Thread: The Assignment Problem

1. Member Join Date
Feb 2009
Posts
9
Rep Power
0 The Assignment Problem

Hello,

I'm trying to figure out how to create a program that will solve the assignment problem. The idea I have is to create a 2D array, with each element holding a cost. Only certain costs would be added up and stored in variables. To calculate the sum of the costs I need to come up with a way to generate all the combinations.

I don't know how to explain it very well, so I made tables to show what I mean.

For example, a 3x3 matrix will produce 6 possible combinations, here are 2 of the combinations:

Java Code:

0  1  2
0  X
1     X
2        X

cost1 = Matrix + Matrix + Matrix

Java Code:

0  1  2
0  X
1        X
2     X

cost2 = Matrix + Matrix + Matrix

(Sorry for the code fragments, couldn't think of anything else.)

Would appreciate any help, thx!

I'll try to explain more. I'm trying to generate all solutions where only 1 element in each row is chosen. The element in the next row cannot be in that same column. For example, (0,0) + (1,1) + (2,2) is one combination. (0,2) + (1,1) + (2,0) is another and so on.. Two elements cannot be chosen from the same rows or the same columns. I just can't figure out how to write an algorithm that will be able to give me all combinations correctly. There are a total of 6 combinations for a 3x3 matrix.
Last edited by bumblyb33; 02-27-2009 at 11:26 AM.  Reply With Quote

2. Member Join Date
Feb 2009
Location
Romania
Posts
11
Rep Power
0  Originally Posted by bumblyb33 Hello,

I'm trying to figure out how to create a program that will solve the assignment problem. The idea I have is to create a 2D array, with each element holding a cost. Only certain costs would be added up and stored in variables. To calculate the sum of the costs I need to come up with a way to generate all the combinations.

I don't know how to explain it very well, so I made tables to show what I mean.

For example, a 3x3 matrix will produce 6 possible combinations, here are 2 of the combinations:

Java Code:

0  1  2
0  X
1     X
2        X

cost1 = Matrix + Matrix + Matrix

Java Code:

0  1  2
0  X
1        X
2     X

cost2 = Matrix + Matrix + Matrix

(Sorry for the code fragments, couldn't think of anything else.)

Would appreciate any help, thx!
hello!

I do not see where is the assignment problem ???
The cost variable must be of same type that matrices elements!

regards  Reply With Quote

3. uhmm try using a List either ArrayList or LinkedList .. but i im not 100% sure on what you are trying to do can you provide a more detailed explanation?  Reply With Quote

4. Senior Member Join Date
Sep 2008
Posts
564
Rep Power
12 pretend you have a one-dimensional array of { 0, 1, 2 }. how would you find all permutations? same principle.  Reply With Quote

5. Member Join Date
Feb 2009
Posts
10
Rep Power
0 more details required....  Reply With Quote

6. hmm... i dont get it..  Reply With Quote Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•