Can anyone help with the below problem statement?
I want to find the maximum sum in a 2D matrix such that:
- You can pick only 1 element from each row
- 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.
