매트릭스 분할

Question

매트릭스가 N <= 25 인 경우 매트릭스가 주어지며 각 셀은 양의 정수 값을 갖습니다. 어떻게 최대 K 라인 (수직 위/아래 라인 또는 직선 왼쪽/오른쪽 라인 [주 : 한쪽에서 다른쪽으로 확장해야한다]) 최대 값 그룹 (파티션에 의해 결정됨)이 최소가되도록? 다음의 행렬

1 1 2 
1 1 2 
2 2 4 

주어 우리가 분할 2 개 라인을 사용할 수있다 예를 들어

, 우리는 열 2와 3 사이의 라인뿐만 아니라, 행 (2) 사이의 선을 그린다 3, 최소화 된 최대 값을 제공합니다.

내 첫 번째 생각은 각 줄의 상태를 나타내는 2 개의 정수를 나타내는 비트 마스크입니다. 그러나 이것은 너무 느립니다. 나는 복잡성이 O(2^(2N))이라고 생각합니다. 행에 대한 해결책을 찾은 다음 열을 해결할 수 있을까요?

누구든지 아이디어가 있습니까?

편집 : 여기에 문제가 내가 봤 후 : http://www.sciencedirect.com/science/article/pii/0166218X94001546

다른 용지 : http://cis.poly.edu/suel/papers/pxp.pdf

I, 즉^

Answer 1

당신은 수직선에 대한 모든 부분 집합을 시도 할 수 있습니다 읽으려고하고있어 그런 다음 수평선에 대해 동적 프로그래밍을 수행하십시오.

수직선 집합을 S로 고정한다고 가정 해 봅시다. 고정 된 수직선 집합 S가 D (K, S) 인 행렬의 첫 번째 K 행으로 구성된 하위 문제에 대한 답을 나타냅니다. 작은 크기의 부분 문제로 D (K, S)를 풀 수있는 재발을 찾는 것은 사소한 일이다.

처음에 각 하위 매트릭스의 크기를 미리 계산할 경우 전반적인 복잡성은 O (2^N * N^2) 여야합니다.