The Assignment Problem

• 02-26-2009, 10:58 PM
bumblyb33
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:

Code:

```    0  1  2        0  X      1    X  2        X cost1 = Matrix[0][0] + Matrix[1][1] + Matrix[2][2]```

Code:

```    0  1  2        0  X  1        X  2    X cost2 = Matrix[0][0] + Matrix[1][2] + Matrix[2][1]```

(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.
• 02-26-2009, 11:42 PM
JVposter
Quote:

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:

Code:

```    0  1  2        0  X      1    X  2        X cost1 = Matrix[0][0] + Matrix[1][1] + Matrix[2][2]```

Code:

```    0  1  2        0  X  1        X  2    X cost2 = Matrix[0][0] + Matrix[1][2] + Matrix[2][1]```

(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
• 02-27-2009, 05:36 AM
azzaiel
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?
• 02-27-2009, 07:49 AM
emceenugget
pretend you have a one-dimensional array of { 0, 1, 2 }. how would you find all permutations? same principle.
• 03-03-2009, 10:24 PM
chrono25
more details required....
• 03-04-2009, 05:21 AM
critdevil
hmm... i dont get it..