Maximum sum in a 2D matrix

Revision en3, by jainpavbhaji, 2023-04-19 08:20:07

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English jainpavbhaji 2023-04-19 08:20:07 0 (published)
en2 English jainpavbhaji 2023-04-19 07:42:07 4 (saved to drafts)
en1 English jainpavbhaji 2023-04-19 07:41:15 858 Initial revision (published)