iyi yolu (Java kullanarak ancak algoritma burada konudur)

Question

Ben kullanılacak doğru terminolojiyi bilmiyorum ama bu

1 3 4 
5 4 5 
2 2 5 

gibi bir 3x3 matris var ve istediğim Maalesef Her satır/sütundan bir değer seçerek en yüksek puanı al ama aynı satır veya sütunu bir kereden fazla alamıyorum, bu durumda yanıt

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

4 + 5 + 5 = 14'e izin verilmez, çünkü col'den iki değer seçerdi 2

Java kullanıyorum ve genellikle matris boyutu 15 x 15 olacaktır.

orada Im algoritmasını yapmaya çalışıyor ve whats için ne bir isim var mı

teşekkür Paul

DÜZENLEME: Not: Macar algoritması sadece satır hiçbir cols hiçbir eşit olduğunda çalışır ve de benim Bu durum her zaman geçerli değil, 10x12 veya 11x13 vakalarım var. Ancak görünür, ekstra kukla satırları ekleyerek bunu elde edebilirsiniz.

DÜZENLEME hmm bu implmentations birini denediğiniz ve Geniune Im Bu assignment problem var o

 
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

misreading sürece çalışmıyor gibi görünüyor doesnt. Satırlara "insanlar" ve sütunları "ödevler" olarak bakabilirsiniz. Her bir kişinin matrix[i][j] money için bir görev yapabildiği toplam maliyeti en aza indirgemek (en üst seviyeye çıkarmak istiyorsunuz ama fikir kalır).

hungarian algorithm iyi bir çözümdür, ancak oldukça karmaşıktır. Bence, 15x15 matrislerde gayet iyi çalışır.

Answer 2

15x15 için, Dynamic Programming alanını O(N 2^N) saat, O(2^N) alanında kullanabilirsiniz.

/* 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; 
} 

gerektiğinde öncü takip edin: fikir bit maskesi, (C) gibi bir şey kadar sen hangi satırı dolaylı kullanılır ve hangi sütunun açıkça belirten ile DP kullanmaktır. Bu 20'li yaşlara kadar çalışmalı.

Daha büyük N s için, Vlad'ın önerilerini dikkate almalısınız.