There's no need to approximate. You can efficiently find the maximum
sum by brute force, that is, by finding all possible sums. To
economize on memory, we store only the best sum found so far.
If we want to find feasible combinations of matrix elements, it helps
to have the following insight: given that the matrix has dimensions
n*m, i.e., n rows and m columns, with the condition that n is less
than or equal to m, a valid sum may only include one element from each
row. Think about that for a minute. It means that for an n*m matrix, a
feasible sum will consist of exactly n terms, where each term is drawn
from a different column. (If we are given a matrix that has more rows
than columns, we simply transpose it to obtain a matrix that meets the
requirement n <= m.)
The following program requires that you pass it the dimensions of a
matrix and the name of a file containing whitespace-separated matrix
elements.
//begin MatrixSum.java
import java.io.*;
import java.util.*;
public class MatrixSum {
static int n, m;
static double bestsum;
static double[][] mat;
static boolean[] used;
static void best(int i, double sum) {
if (i == n) {
if (sum > best)
bestsum = sum;
return;
}
for (int j = 0; j < m; j++)
if (!used[j]) {
used[j] = true;
best(i+1, sum+mat[i][j]);
used[j] = false;
}
}
static void error(String msg) {
System.out.println(msg);
System.exit(0);
}
public static void main(String[] argv) {
int i, j, imax = 0, jmax = 0;
boolean transpose = false;
BufferedReader in = null;
String str = "", line = "";
StringTokenizer tokenizer;
if (argv.length != 3)
error("usage: java MatrixSum <n> <m> <filename>");
try {
imax = n = Integer.parseInt(argv[0]);
jmax = m = Integer.parseInt(argv[1]);
if (n > m) {
n -= m;
m += n;
n = m-n;
transpose = true;
}
} catch (NumberFormatException e) { error("error: integers
required"); }
try {
in = new BufferedReader(new FileReader(argv[2]));
} catch (IOException e) { error("error: missing file"); }
try {
while ((line = in.readLine()) != null)
str += line + " ";
} catch (IOException e) { error("bad file"); }
tokenizer = new StringTokenizer(str, " \t\n\r\f");
if (tokenizer.countTokens() != n*m)
error("" + n*m + " values required; only have " +
tokenizer.countTokens());
mat = new double[n][m];
used = new boolean[m];
try {
for (i = 0; i < imax; i++)
for (j = 0; j < jmax; j++)
if (transpose)
mat[j][i] =
Double.parseDouble(tokenizer.nextToken());
else
mat[i][j] =
Double.parseDouble(tokenizer.nextToken());
} catch (Exception e) { error("bad number"); }
for (i = 0; i < m; i++)
used[i] = false;
bestsum = Double.MIN_VALUE;
best(0, 0.0);
System.out.println("best sum = " + bestsum);
}
}
//end MatrixSum.java
Don't be intimidated by the length of this program. You'll find upon
closer inspection that the vast majority of it consists of string
processing and attempts to catch various user errors, since I've tried
to make it reasonably robust.
The real work is done by the recursive function best(). Let me
describe what takes place before, during, and after its execution. By
the time we reach the line "bestsum = Double.MIN_VALUE;", the
two-dimensional array mat[][] will have been filled with n rows and m
columns such that n < m. We also have a boolean array used[] of size
m, with all elements initialized to false. Since we have yet to
calculate any sum, we initialize bestsum to the smallest sum that can
conceivably be obtained. We now call best() with the arguments 0 and
0.0, telling it that we want to choose an element from row 0 and that
our running sum is 0.0 so far.
The function best() first asks whether we have exhausted all rows of
the matrix. If so, we compare the running sum to the best sum, and, if
necessary, update the latter. Otherwise, we have to choose an element
from the current row. We iterate over the row, considering each column
number. If the array used[] tells us that we have already chosen an
element from that column, we move on. Otherwise, we set the
corresponding element of used[] to true, add the matrix element from
this column to our running sum, increment the row number, and make a
recursive call to best(). In effect, we have made our choice, and are
now moving on to the next row. Upon returning from the recursive call,
we are back at our current row and column number. We reset the used[]
element to false, and continue to the next column.
And that's it. Once we've returned from the original call to best(),
every feasible sum will have been evaluated, and we are assured that
the highest one has been assigned to bestsum.
There is a more efficient way to calculate the best sum, involving a
stack, but it's computationally equivalent to the recursive solution.
I'm afraid a general explanation of recursivity lies beyond the scope
of your question, but I trust you'll be satisfied with this solution
to your immediate problem.
Regards,
leapinglizard |
Clarification of Answer by
leapinglizard-ga
on
10 Nov 2002 08:58 PST
The brute-force algorithm computes C(m,n)*n! =
m*(m-1)*(m-2)*...*(m-n+1) sums, which may, indeed, take quite a while.
For a 12x10 matrix, for example, we have C(m,n)*n! = 66*3628800 =
239,500,800 sums.
We can speed up the work somewhat by considering, among the m elements
in a given row, only the n greatest ones. Now, we compute n! sums,
which, in the example above, yields 10! = 3,628,800. This is still a
formidable number on a human scale, but more manageable
computationally. Code follows.
//begin MatrixSum.java
import java.io.*;
import java.util.*;
public class MatrixSum {
static int n, m;
static double bestsum;
static double[][] mat;
static boolean[][] top;
static boolean[] used;
static void best(int i, double sum) {
if (i == n) {
if (sum > bestsum)
bestsum = sum;
return;
}
for (int j = 0; j < m; j++)
if (top[i][j] && !used[j]) {
used[j] = true;
best(i+1, sum+mat[i][j]);
used[j] = false;
}
}
static void error(String msg) {
System.out.println(msg);
System.exit(0);
}
public static void main(String[] argv) {
int i, j, imax = 0, jmax = 0;
double[] row;
boolean transpose = false;
BufferedReader in = null;
String str = "", line = "";
StringTokenizer tokenizer;
if (argv.length != 3)
error("usage: java MatrixSum <n> <m> <filename>");
try {
imax = n = Integer.parseInt(argv[0]);
jmax = m = Integer.parseInt(argv[1]);
if (n > m) {
n -= m;
m += n;
n = m-n;
transpose = true;
}
} catch (NumberFormatException e) { error("error: integers
required"); }
try {
in = new BufferedReader(new FileReader(argv[2]));
} catch (IOException e) { error("error: missing file"); }
try {
while ((line = in.readLine()) != null)
str += line + " ";
} catch (IOException e) { error("bad file"); }
tokenizer = new StringTokenizer(str, " \t\n\r\f");
if (tokenizer.countTokens() != n*m)
error("" + n*m + " values required; only have " +
tokenizer.countTokens());
mat = new double[n][m];
top = new boolean[n][m];
used = new boolean[m];
try {
for (i = 0; i < imax; i++)
for (j = 0; j < jmax; j++)
if (transpose)
mat[j][i] =
Double.parseDouble(tokenizer.nextToken());
else
mat[i][j] =
Double.parseDouble(tokenizer.nextToken());
} catch (Exception e) { error("bad number"); }
for (i = 0; i < n; i++) {
row = mat[i];
Arrays.sort(row);
for (j = 0; j < m; j++)
if (Arrays.binarySearch(row, mat[i][j]) < n)
top[i][j] = true;
else
top[i][j] = false;
}
for (i = 0; i < m; i++)
used[i] = false;
bestsum = Double.MIN_VALUE;
best(0, 0.0);
System.out.println("best sum = " + bestsum);
}
}
//end MatrixSum.java
Further optimizations are possible, but they require increasing
algorithmic sophistication. If you find that this crude pruning is
inadequate, I'd like you to give me an idea of the size and
composition of your problem instances.
Regards,
leapinglizard
|
,
3 Comments
)