Cách tốt nhất để có được số tiền cao nhất từ ​​một ma trận (sử dụng Java nhưng thuật toán là vấn đề ở đây)

Question

Xin lỗi tôi không biết thuật ngữ đúng để sử dụng nhưng tôi có một ma trận 3x3 như thế này

1 3 4 
5 4 5 
2 2 5 

và tôi muốn có được điểm số cao nhất bằng cách chọn giá trị từ mỗi hàng/cột nhưng tôi không thể chọn cùng một hàng hoặc cột nhiều lần, do đó câu trả lời trong trường hợp này là

3 + 5 + 5 = 13 (row0, col1 + row1 , col0 + row2, col2)

4 + 5 + 5 = 14 không được phép vì đã chọn hai giá trị từ col 2

Tôi đang sử dụng Java và thường ma trận sẽ có kích thước 15 x 15.

Có một tên cho những gì Im cố gắng để làm, và whats thuật toán

nhờ Paul

EDIT: Lưu ý: các thuật toán hungarian chỉ hoạt động khi không có hàng bằng không của cols, và trong tôi trường hợp này không phải luôn luôn là trường hợp tôi thường xuyên có các trường hợp 10x12 hoặc 11x13. Nhưng nó xuất hiện bạn có thể làm tròn điều này bằng cách thêm các hàng giả.

EDIT hmm, cố gắng ra một trong những implmentations và nó không có vẻ alwasy để làm việc, trừ khi Im hiểu sai nó

 
100.0,100.0,100.0,100.0,30.0,80.0,80.0,100.0,100.0,80.0, 
80.0,100.0,100.0,100.0,80.0,80.0,25.0,100.0,100.0,80.0, 
80.0,100.0,100.0,100.0,80.0,25.0,80.0,100.0,100.0,80.0, 
100.0,25.0,80.0,100.0,100.0,100.0,100.0,100.0,100.0,100.0, 
0.0,100.0,100.0,100.0,100.0,80.0,80.0,100.0,100.0,100.0, 
100.0,100.0,100.0,100.0,100.0,100.0,100.0,100.0,25.0,100.0, 
100.0,100.0,100.0,25.0,100.0,100.0,100.0,75.0,100.0,100.0, 
100.0,80.0,30.0,100.0,75.0,100.0,100.0,100.0,100.0,100.0, 
100.0,100.0,100.0,100.0,80.0,80.0,80.0,100.0,100.0,25.0, 
100.0,100.0,100.0,75.0,100.0,100.0,100.0,25.0,100.0,100.0, 
Results calculated 
0:4,0, 
1:3,1, 
2:7,2, 
3:6,3, 
4:0,4, 
5:2,5, 
6:1,6, 
7:9,7, 
8:5,8, 
9:8,9, 

Answer 1

Đó là assignment problem. Bạn có thể xem các hàng là "người" và các cột là "bài tập". Bạn muốn giảm thiểu (tốt, bạn muốn tối đa hóa nhưng ý tưởng vẫn là) tổng chi phí, trong đó mỗi người có thể thực hiện một nhiệm vụ cho matrix[i][j] money.

hungarian algorithm là một giải pháp tốt, nhưng nó khá phức tạp. Tôi nghĩ rằng bruteforcing nó sẽ làm việc tốt trên các ma trận 15x15.

Answer 2

Đối với 15x15, bạn có thể sử dụng Dynamic Programming trong không gian O(N 2^N), O(2^N). Ý tưởng là để sử dụng DP với một bitmask chỉ ra một cách rõ ràng mà cột được sử dụng, và mặc nhiên mà hàng bạn đang lên đến, một cái gì đó tương tự (trong C):

/* used, cache arrays of size 1 << N, used initialized to 0 */ 

/* max_sum(0, 0) is the starting point. Row is implicit, but 
    here to make things easier. */ 
int max_sum(int row, int bitmask) { 
     /* Base case - the number of rows */ 
     if (row == num_row) return 0; 

     /* If we've already seen this bitmask */ 
     if (used[ bitmask ]) return cache[ bitmask ]; 
     int max_current = 0, i; 

     for (i = 0; i < N; i++) 
      /* If column "i" is not used */ 
      if ((bitmask & (1 << i)) == 0) 
       max_current = max( 
          /* Use column i on this row, mark column as used 
            on the bitmask, go on to the next row. */ 
          max_sum(row + 1, bitmask | (1 << i)) 
           + cell[row][i], 
          max_current) 

     /* Save the cache down */ 
     used[ bitmask ] = 1; 
     return cache[ bitmask ] = max_current; 
} 

Theo dõi các tiền thân khi cần thiết. Điều này sẽ làm việc lên đến 20s thấp.

Để lớn hơn N s, bạn nên xem xét đề xuất của Vlad.