Partitioning a matrix
Given a matrix N x N
where N <= 25
, and each cell has a positive integer value, how can you break it down into no more than K rows (with straight up / down or straight left / right lines [note: they must extend from one side to the other]) so that the maximum group of values (as defined by the partitions) is the minimum?
For example, given the following matrix
1 1 2
1 1 2
2 2 4
and we are allowed to use 2 lines to split it, we have to draw a line between columns 2 and 3 and also a line between lines 2 and 3 that gives the minimum maximum value of 4.
My first thought would be a bitmask representing the state of each line, with two integers to represent it. However, this is too slow. I think the difficulty is O(2^(2N))
Maybe you can solve it for rows and then solve it for columns?
Does anyone have any idea?
Edit: here is the problem after I found it on google: http://www.sciencedirect.com/science/article/pii/0166218X94001546
another article: http://cis.poly.edu/suel/papers/pxp.pdf
I'm trying to read that ^
source to share
You can try all subsets for vertical lines and then do dynamic programming for horizontal lines.
Let's say you have fixed the set of vertical lines as S. Let's denote the answer for a subproblem consisting of the first K rows of a matrix with a fixed set of vertical lines S as D (K, S). Then it is trivial to find repetition for the solution D (K, S) with smaller subproblems.
The total complexity should be O (2 ^ N * N ^ 2) if you first copy the dimensions of each submatrix at the beginning.
source to share