Maximum sum in a 2D matrix

Правка en2, от jainpavbhaji, 2023-04-19 07:42: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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский jainpavbhaji 2023-04-19 08:20:07 0 (published)
en2 Английский jainpavbhaji 2023-04-19 07:42:07 4 (saved to drafts)
en1 Английский jainpavbhaji 2023-04-19 07:41:15 858 Initial revision (published)