Howdy, Stranger!

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

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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.