행렬의 각 행과 열에서 하나의 요소를 선택하면 합계가 최소화됩니다.

Question

NxN 양의 정수 행렬이 있고 각 행과 열에서 정확히 하나의 요소를 선택하라는 메시지가 표시되므로 선택된 행과 열의 합이 요소가 최소화되면 어떻게 해결 될 수 있습니까?

저는 동적 프로그래밍에 관한 것이라고 생각합니다. 이것은 현재의 행렬의 행 0에서 요소를 선택하고, 다음 행렬을 분할하고 서브 매트릭스를 해결하기 위해 자신을 재귀 적으로 호출

Dictionary<byte[,], int>[] memo = new Dictionary<byte[,], int>[17]; 

    int rec(byte[,] arr) 
    { 
     if (arr.Length == 1) return arr[0, 0]; 
     int opt = find(arr); 
     if (opt != -1) return opt; 
     opt = 1 << 25; 
     for (int i = 0; i < arr.GetLength(1); ++i) 
      opt = Math.Min(opt, arr[0, i] + rec(divide(arr, i))); 
     add(arr, opt); 
     return opt; 
    } 

: I 시간 O(n!) 사용 메모이 제이션을 최소화하기 위해 노력했다. 함수 divide은 선택한 요소에 따라 현재 행렬을 나눕니다. 서브 - 매트릭스 크기는 (N-1) x (N-1)이다. 함수 find은 memo[n]에서 선형 검색을 수행하고 add은 솔루션을 memo[n]에 추가합니다. 그러나 각 행렬을 다른 행렬과 비교하기에는 너무 느립니다.

일부 불만 사항이 있습니까? 더 빠른 DP 알고리즘이 있습니까? 1 + 5 + 10 + 14

단계 :

7 6 5 

11 10 12 

14 16 15 

---

11 10 

14 16 

---

012 어떤 도움

예

1  2  3 4 

8  7  6 5 

9  11 10 12 

13 14 16 15 

최적 솔루션을 알 수있다

14 

Answer 1

실제로는 assignment problem입니다. 다른 방법들 중에서도 Hungarian algorithm,을 사용하여 다항식 시간으로 풀 수 있습니다.