Matrix Maximization

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.

Comment on Matrix Maximization

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]
Re: Re: Matrix Maximization by BrowserUk (Patriarch) on Dec 23, 2002 at 20:07 UTC
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]


Pathologically Eclectic Rubbish Lister
	PerlMonks