jainpavbhaji's blog

Maximum sum in a 2D matrix
By jainpavbhaji, history, 19 months ago, In English

Can anyone help with the below problem statement?

I want to find the maximum sum in a 2D matrix such that:

  1. You can pick only 1 element from each row
  2. You cannot pick a column that has been picked before.

Example:

matrix = [ [12, 1, 1, 1], [13, 10, 1, 1], [40, 1, 1, 12] ]

Solution:

We pick 12 from 1st row

Now we cannot pick 13 from 2nd row as the column has already been used. Therefore, will pick 10 in 2nd row

Now we can either pick 1 or 12 from 3rd row as 1st and 2nd columns have already been used. We will pick 12 in 3rd row

So, sum = 12 + 10 + 12 = 34

This is not the maximum answer.

Max. answer = 1 + 10 + 40 = 51.

Can we solve this using Hungarian algorithm? Are there any better options? Kindly help.

Note: This is not a problem of any ongoing contest.

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
19 months ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

What is the problem constraints? If either dimension of the matrix is small (less than $$$15$$$, or somewhere around that), then the problem can be easily solved using dp bitmask. If it was bigger, then you would have to use maximum weight matching, which is quite advanced.

→ Reply
»
19 months ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

Yes you can , consider the given matrix in the input as "M" , you can create a bipartite graph where the nodes on the left represent the X axis and the nodes on the right represent the Y axis , the edge between the ith node from the left part and the jth node from the right will have the weight M[i][j] , this setup should prevent you from choosing a cell that has a row or a column that has been picked by a cell you chose before. I am not sure but ig the Hungarian algorithm finds perfect matching so you might want to fix that by copying the graph and adding a zero weight edge between each node and its copy in the copied graph. In the final graph you can apply the Hungarian algorithm and get the answer.

I am not sure if there is any better way to find an answer for the maximum weight matching problem other than hungarian algorithm.

UPDATE : it turns out hungarian algorithm already has a version which works on matrices so there is no reason to convert the matrix into a weighted bipartite graph. You can just apply the conventional algorithm which already works for matrices , sorry for the inconvenience

→ Reply