## Algorithms

Moderators: None (Apply to moderate this forum)
Number of posts: 762

This Forum Only

Finding the maximum sum from a 2D array with a catch Posted by ronsz on 1 Nov 2002 at 5:45 AM
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

Re: Finding the maximum sum from a 2D array with a catch Posted by cherio on 6 Nov 2002 at 4:32 AM
: 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) {
}
}
}

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic