Finding the maximum sum from a 2D array with a catch - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Finding the maximum sum from a 2D array with a catch

ronszronsz Posts: 2Member
Hi,
I'm trying to find an algorithm in Java that determines the maximum result from adding together a combination of row column values in a 2D array. The limitation is that once a particular (row,column) value is chosen, no other entries in that row or column can be used in the calculation.

e.g. The 2D array below would return the maximum value of

c0 c1 c2
r0 1 4 7
r1 3 6 8

All possible combinations are:
1+6 = 7
1+8 = 9
4+3 = 7
4+8 = 12
7+3 = 10
7+6 = 13

So the maximum result is 12.
I have an algorithm at the moment that can find all these combinations and select the best one but it is very inefficient and uses up too much memory. It keeps track of all the possible combinations.

If anyone can help it would be greatly appreciated.
Cheers,
Ron

Comments

  • cheriocherio Posts: 33Member
    : Hi,
    : I'm trying to find an algorithm in Java that determines the maximum result from adding together a combination of row column values in a 2D array. The limitation is that once a particular (row,column) value is chosen, no other entries in that row or column can be used in the calculation.
    :
    : e.g. The 2D array below would return the maximum value of
    :
    : c0 c1 c2
    : r0 1 4 7
    : r1 3 6 8
    :
    : All possible combinations are:
    : 1+6 = 7
    : 1+8 = 9
    : 4+3 = 7
    : 4+8 = 12
    : 7+3 = 10
    : 7+6 = 13
    :
    : So the maximum result is 12.
    : I have an algorithm at the moment that can find all these combinations and select the best one but it is very inefficient and uses up too much memory. It keeps track of all the possible combinations.
    :
    : If anyone can help it would be greatly appreciated.
    : Cheers,
    : Ron
    :
    :

    I don't know how efficient this solution is, but two tier loop, should
    do it, for starters
    for(row = 0; row < rowcount; row++) {
    for(column = 0; column < colmncount; column++) {
    if(column != row) {
    /* your operation */
    }
    }
    }
Sign In or Register to comment.