CODEWITHSUNDEEP
dynamic-programming
user2938723
user2938723

Reputation: 1130

Dynamic Programming-Find the maximum possible sum in a 2D matrix

Find the maximum possible sum in a 2D matrix such that if element[i][j] is selected then the next element cannot be selected again from the same ith row or jth column.

example 3*3 matrix

 6.0   7.0    6.0
 4.5   6.0   6.75
 6.0   5.0   9.0

Here maximum sum is 21 because 6.0(1st row)+6.0(2nd row)+9.0(3rd row)=21 We cannot select 7.0(1st row)+6.75(2nd row)+9.0(3rd row) because 6.75 and 9.0 lie in the same column.

I understand its a dynamic programming problem. What would be an algorithm for this?

Upvotes: 1

Views: 2256

Answers (2)

string_is_hard
string_is_hard

Reputation: 29

If I understand correctly, this is essentially an assignment problem which can be solved by the Hungarian algorithm. You just need to convert the maximum goal to a minimum goal by either subtract all elements from the global maximum or negate them.

Upvotes: 0

John
John

Reputation: 1490

Given the fact that you cannot re-use a column or row, your sums are going to be diagonal lines. Here is my first stab at an algorithm (in pseudocode):

our largest known sum is 0.

for(0 to columncount-1)
    sum element[0][column]'s diagonal (i.e. 6.0 + 6.0 + 9.0, then 7.0 + 6.75, then 6.0)
    if it's greater than our largest sum, it becomes the largest sum and we track those elements.
for(1 to rowcount-1)
    sum element[row][0]'s diagonal (i.e. 4.5 + 5.0, then 6.0)
    if it's greater than our largest sum, it becomes the largest sum and we track those elements.

Then you need to repeat going the other way (i.e. right-left, then top-bottom).

I don't know if that makes sense, but that algorithm will give you the largest combination, for any rectangular matrix.

Upvotes: 1

Related Questions