artist has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks

How I can eliminate rows in a given matrix such that it maximize the sum of the numbers in matrix and sum of numbers in each column should not exceed a given constant.

My First Apporach
1. Take all the possible combination of rows.
2. Have each combination calculate the column sum, discard the combination if any of them has colmun-sum exceeds the constant.
3. Figure out the best combination as maximum matrix-sum.
I appreciate Any other Approach.

Thanks,
Artist.

Replies are listed 'Best First'.
Re: Matrix Maximization
by I0 (Priest) on Dec 24, 2002 at 09:55 UTC
    This problem can be reduced from knapsack, which is NP-Complete
[reply]
Re: Matrix Maximization
by artist (Parson) on Dec 23, 2002 at 19:43 UTC

    Here is an example:
    The column max constant: 12

  1 2 3 (Columns)
  =====
A|3 4 7
B|4 5 3
C|8 3 2

Combinations:values
ABC: Cannot take because Column1: 3+4+8 > 12 (Column-Max)
AB: 7+9+10 => 26
AC: 11+7+9 => 27
BC: 12 +8 +5 = 25

    Since A, B and C all are involved in above, we dont' need to count seperate combination-values for them.
    Thus AC is the best combination::::
    So 'Eliminate B'.
[reply]

      A few questions:

      Is the size of the matrices fixed or variable?

      What limitations are you encountering with your current approach?

      Is performance an issue beyond: "It would be nice if it went quicker"?

      And an unnecessary one, just because I'm intrigued - what's the problem your solving?

      Examine what is said, not who speaks.

[reply]
Re: Matrix Maximization
by CountZero (Bishop) on Dec 24, 2002 at 06:54 UTC

    Although I'm no mathematician, I have a feeling that this kind of problem will only yield to a brute-force approach, i.e. working out all combinations of rows and calculating the value of the matrix and then checking the column-constraint.

    CountZero

    "If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

[reply]

Back to Seekers of Perl Wisdom