kburnik

C++ - Zadatak Kule (rješenje s komentarima)

Mar 1st, 2013
81
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Zadatak: Kule
  3.            
  4.              http://bit.ly/zadatak-kule
  5.    
  6.     Složenost: << faktorijelna zbog memoizacije!
  7.  
  8.     Datum: 2013-03-01
  9.  
  10.     Autor: Goran Žužić, HSIN
  11.    
  12.     Ponuđeno rješenje: Kristijan Burnik, udruga informatičara Božo Težak
  13.  
  14.     Gmail: kristijanburnik
  15.  
  16. */
  17. #include <iostream>
  18. #include <cstdlib>
  19. #include <cmath>
  20.  
  21. using namespace std;
  22.  
  23. // matrica koja predstavlja šahovnicu
  24. int a[20][20];
  25.  
  26. // red veličine šahovnice
  27. int n;
  28.  
  29. // memoizacijska mapa koja čuva već izračunate maksimalne sume
  30. // uzimamo ukupno 1048576 integera ~ 4 MB memorije
  31. // što je binarno : 1 0000 0000 0000 0000 0000
  32. // to je shift jedinice za 20 mjesta udesno jer max N = 20 !
  33. // Primjerice ako je N = 3, onda možemo pamtiti maksimume
  34. // redom za 011, 110, 101, 111, tj sve kombinacije odabira stupaca!
  35. int sums[0x100000] = {0};
  36.  
  37. // rekurzivna funkcija s memoizacijom
  38. int maxsuma(int free,int size) {
  39.  
  40.    ///////////////////////////////////////////////////////////////////////////
  41.    // optimizacijski dio: ako već imamo rezultat, onda ga vraćamo
  42.    //
  43.    // primjetiti da free promatramo kao bitove koji oznacavaju odabir stupaca!
  44.    // npr ako je size = 3 i spremljen je rezultat za free = 1101
  45.    // onda smo vec zapamtili rjesenje za stupce 0, 2 i 3 u zadnja 4 reda ploce
  46.    int saved = sums[free];
  47.    // zakomentirati donji redak kod testiranja rada bez memoizacije!
  48.    if (saved > 0) return saved;
  49.  
  50.    ///////////////////////////////////////////////////////////////////////////
  51.    // Trivijalni izračun :: kad je promatrani segment ploče 2x2
  52.    
  53.    if (size == 2) {
  54.         int r[2] = {n-2,n-1}; // uzimamo zadnja dva retka ploče
  55.         int c[2] = {0,0};    // koje stupce uzimamo? To određuju bitovi FREE
  56.         int cc = 0;       // koliko smo stupaca pronasli?
  57.        
  58.         // prepisemo bitove koje smo primili kao parametar
  59.         int bits = free;
  60.        
  61.         // prolazimo kroz primljene bitove
  62.         // i trazimo prva dva koja su postavljena na 1
  63.         // njihovi indeksi oznacavaju redne brojeve stupaca
  64.         // za koje racunamo maksimum
  65.         for (int i = 0; i < n && cc<2; i++) {
  66.            
  67.             // and operacija sa 1 je zapravo citanje najdesnijeg bita!
  68.             if (bits & 1) {
  69.                 c[cc] = i; // pronasli smo indeks stupca koje je postavljen
  70.                 cc++;
  71.             }
  72.             // pomicemo bitove za jedno mjesto udesno (desni shift)
  73.             // kako bi u iducem krugu opet citali najdesniji bit
  74.             // tj. onaj koji je za jedan lijevo od trenutnog
  75.             bits >>= 1;
  76.         }
  77.        
  78.         // trazimo maksimum za situaciju tipa:
  79.         // 7 6  (r0,c0) (r0,c1)
  80.         // 3 4  (r1,c0) (r1,c1)
  81.         // pa ispitujemo da li je vece (7 + 4) ili (3 + 6) ?
  82.         // veca suma od te dvije jest trivijalno rjesenje
  83.         // njega memoiziramo i odmah vracamo
  84.        
  85.         return (
  86.             sums[free] =
  87.                 max (
  88.                     a[ r[0] ][ c[0] ] + a[ r[1] ][ c[1] ] ,
  89.                     a[ r[1] ][ c[0] ] + a[ r[0] ][ c[1] ]
  90.                 )
  91.             );
  92.    }
  93.  
  94.     ///////////////////////////////////////////////////////////////////////////
  95.    // bazicni slucaj :: promatramo 3 ili vise stupca
  96.  
  97.    // redak koji promatramo je za size odmaknut od kraja ploce
  98.    int r = n - size;
  99.    
  100.    // maksimalna suma ce biti spremljena na max
  101.    int max = 0;
  102.    
  103.    // prepisujemo bitove
  104.    int bits = free;
  105.  
  106.    // koliko smo nabrojali jedinica u bitovima?
  107.    int onecount = 0;
  108.  
  109.    // u bitovima bits nam pise koje stupce smo odabrali
  110.    // npr. kombinacija 1101 znaci da smo odabrali stupce 0,2,3
  111.    // citamo bitove s desna na lijevo!
  112.    
  113.    for (int i = 0; i < n && onecount < size; i++) {
  114.         // radimo samo za one stupce koji su odabrani u varijabli bits!
  115.         if (bits & 1) {
  116.             // racunamo sumu za ovu kombinaciju
  117.             // rekurziji predajemo izvorno dobivene bitove
  118.             // ali brisemo iz njih stupac na i-tom mjestu
  119.             // npr. ako je varijabla free = 1101, a i = 3, onda predajemo 0101
  120.             // (1 << i) postavlja bit na i-to mjesto gledano s desna, ostalo je 0
  121.             // oduzimanjem se taj bit prebrise! npr. 1101 - 1000 = 0101
  122.             int suma = a[r][i] +  maxsuma(free - (1 << i), size - 1);
  123.            
  124.             // utvrdjujemo (novi) maksimum
  125.             if (suma > max) max = suma;
  126.            
  127.             // brojimo da je ovaj bit bio postavljen u jedinicu
  128.             // tako da ne moramo prolaziti svih n bitova ako radimo s manje od n
  129.             onecount++;
  130.         }
  131.         // shiftamo bitove -> pomak na iduci stupac
  132.         bits >>= 1;
  133.     }
  134.    
  135.     // for petlja zapravo radi sljedece (npr. za size = 3 i n = 3):
  136.     //
  137.     // (x) je a[r][i] odnosno trenutno promatrana ćelija
  138.     // [y] je slučaj koji razriješava rekurzivni poziv
  139.     // traži se maksimum (x) + [y]
  140.     //
  141.     // maxsuma( 011 , 2 )  maxsuma( 101 , 2 )   maxsuma( 110 , 2 )
  142.     //
  143.     // (1)  2   3           1  (2)  3             1   2  (3)
  144.     //  4  [5] [6]         [4]  5  [6]           [4] [5]  6
  145.     //  7  [8] [9]         [7]  8  [9]           [7] [8]  9
  146.    
  147.     // memoiziraj i vrati rezultat
  148.     return sums[free] = max ;
  149. }
  150.  
  151. int main(void) {
  152.  
  153.     // unesi red veličine šahovske ploče
  154.     cin >> n;
  155.    
  156.     // unesi sve brojeve na šahovskoj ploči
  157.     for (int i = 0 ; i < n; i++)
  158.         for (int j = 0 ; j < n; j++)
  159.             cin >> a[i][j];
  160.  
  161.     // na pocetku odabiremo da zelimo racunati za sve stupce od 0 do (n-1)
  162.     // shiftamo bitove za n mjesta ulijevo i na kraju oduzmemo 1
  163.     // time osiguravmo da je n najnižih bitova u jedinici, a ostali u 0
  164.     // ako je N = 5 tada se događa sljedeće:
  165.     // 000001
  166.     // 000010 nakon 1. shifta
  167.     // 000100 nakon 2. shifta
  168.     // 001000 nakon 3. shifta  
  169.     // 010000 nakon 4. shifta
  170.     // 100000 nakon 5. shifta
  171.     // 011111 nakon -1  
  172.     int free = (1 << n) - 1;
  173.    
  174.     // varijabla free označava koje stupce promatramo (1) odnosno ignoriramo (0)
  175.    
  176.  
  177.     // ispisi rezultat rekurzije s memoizacijom
  178.     cout << maxsuma(free,n) << endl;
  179.    
  180.     return 0;
  181. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×