The Assignment Problem

[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:

  
   0  1  2	
0  X      
1     X   
2        X

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

  
   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.

[JVposter]

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:

  
   0  1  2	
0  X      
1     X   
2        X

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

  
   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

[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?

[emceenugget]

pretend you have a one-dimensional array of { 0, 1, 2 }. how would you find all permutations? same principle.

[chrono25]

more details required....

[critdevil]

hmm... i dont get it..