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

/*
    Zadatak: Kule

             http://bit.ly/zadatak-kule

    Složenost: << faktorijelna zbog memoizacije!

    Datum: 2013-03-01

    Autor: Goran Žužić, HSIN

    Ponuđeno rješenje: Kristijan Burnik, udruga informatičara Božo Težak

    Gmail: kristijanburnik

*/
#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

// matrica koja predstavlja šahovnicu
int a[20][20];

// red veličine šahovnice
int n;

// memoizacijska mapa koja čuva već izračunate maksimalne sume
// uzimamo ukupno 1048576 integera ~ 4 MB memorije
// što je binarno : 1 0000 0000 0000 0000 0000
// to je shift jedinice za 20 mjesta udesno jer max N = 20 !
// Primjerice ako je N = 3, onda možemo pamtiti maksimume
// redom za 011, 110, 101, 111, tj sve kombinacije odabira stupaca!
int sums[0x100000] = {0};

// rekurzivna funkcija s memoizacijom
int maxsuma(int free,int size) {

   ///////////////////////////////////////////////////////////////////////////
   // optimizacijski dio: ako već imamo rezultat, onda ga vraćamo
   //
   // primjetiti da free promatramo kao bitove koji oznacavaju odabir stupaca!
   // npr ako je size = 3 i spremljen je rezultat za free = 1101
   // onda smo vec zapamtili rjesenje za stupce 0, 2 i 3 u zadnja 4 reda ploce
   int saved = sums[free];
   // zakomentirati donji redak kod testiranja rada bez memoizacije!
   if (saved > 0) return saved;

   ///////////////////////////////////////////////////////////////////////////
   // Trivijalni izračun :: kad je promatrani segment ploče 2x2

   if (size == 2) {
        int r[2] = {n-2,n-1}; // uzimamo zadnja dva retka ploče
        int c[2] = {0,0};    // koje stupce uzimamo? To određuju bitovi FREE
        int cc = 0;       // koliko smo stupaca pronasli?

        // prepisemo bitove koje smo primili kao parametar
        int bits = free;

        // prolazimo kroz primljene bitove
        // i trazimo prva dva koja su postavljena na 1
        // njihovi indeksi oznacavaju redne brojeve stupaca
        // za koje racunamo maksimum
        for (int i = 0; i < n && cc<2; i++) {

            // and operacija sa 1 je zapravo citanje najdesnijeg bita!
            if (bits & 1) {
                c[cc] = i; // pronasli smo indeks stupca koje je postavljen
                cc++;
            }
            // pomicemo bitove za jedno mjesto udesno (desni shift)
            // kako bi u iducem krugu opet citali najdesniji bit
            // tj. onaj koji je za jedan lijevo od trenutnog
            bits >>= 1;
        }

        // trazimo maksimum za situaciju tipa:
        // 7 6  (r0,c0) (r0,c1)
        // 3 4  (r1,c0) (r1,c1)
        // pa ispitujemo da li je vece (7 + 4) ili (3 + 6) ?
        // veca suma od te dvije jest trivijalno rjesenje
        // njega memoiziramo i odmah vracamo

        return (
            sums[free] =
                max (
                    a[ r[0] ][ c[0] ] + a[ r[1] ][ c[1] ] ,
                    a[ r[1] ][ c[0] ] + a[ r[0] ][ c[1] ]
                )
            );
   }

    ///////////////////////////////////////////////////////////////////////////
   // bazicni slucaj :: promatramo 3 ili vise stupca

   // redak koji promatramo je za size odmaknut od kraja ploce
   int r = n - size;

   // maksimalna suma ce biti spremljena na max
   int max = 0;

   // prepisujemo bitove
   int bits = free;

   // koliko smo nabrojali jedinica u bitovima?
   int onecount = 0;

   // u bitovima bits nam pise koje stupce smo odabrali
   // npr. kombinacija 1101 znaci da smo odabrali stupce 0,2,3
   // citamo bitove s desna na lijevo!

   for (int i = 0; i < n && onecount < size; i++) {
        // radimo samo za one stupce koji su odabrani u varijabli bits!
        if (bits & 1) {
            // racunamo sumu za ovu kombinaciju
            // rekurziji predajemo izvorno dobivene bitove
            // ali brisemo iz njih stupac na i-tom mjestu
            // npr. ako je varijabla free = 1101, a i = 3, onda predajemo 0101
            // (1 << i) postavlja bit na i-to mjesto gledano s desna, ostalo je 0
            // oduzimanjem se taj bit prebrise! npr. 1101 - 1000 = 0101
            int suma = a[r][i] +  maxsuma(free - (1 << i), size - 1);

            // utvrdjujemo (novi) maksimum
            if (suma > max) max = suma;

            // brojimo da je ovaj bit bio postavljen u jedinicu
            // tako da ne moramo prolaziti svih n bitova ako radimo s manje od n
            onecount++;
        }
        // shiftamo bitove -> pomak na iduci stupac
        bits >>= 1;
    }

    // for petlja zapravo radi sljedece (npr. za size = 3 i n = 3):
    //
    // (x) je a[r][i] odnosno trenutno promatrana ćelija
    // [y] je slučaj koji razriješava rekurzivni poziv
    // traži se maksimum (x) + [y]
    //
    // maxsuma( 011 , 2 )  maxsuma( 101 , 2 )   maxsuma( 110 , 2 )
    //
    // (1)  2   3           1  (2)  3             1   2  (3)
    //  4  [5] [6]         [4]  5  [6]           [4] [5]  6
    //  7  [8] [9]         [7]  8  [9]           [7] [8]  9

    // memoiziraj i vrati rezultat
    return sums[free] = max ;
}

int main(void) {

    // unesi red veličine šahovske ploče
    cin >> n;

    // unesi sve brojeve na šahovskoj ploči
    for (int i = 0 ; i < n; i++)
        for (int j = 0 ; j < n; j++)
            cin >> a[i][j];

    // na pocetku odabiremo da zelimo racunati za sve stupce od 0 do (n-1)
    // shiftamo bitove za n mjesta ulijevo i na kraju oduzmemo 1
    // time osiguravmo da je n najnižih bitova u jedinici, a ostali u 0
    // ako je N = 5 tada se događa sljedeće:
    // 000001
    // 000010 nakon 1. shifta
    // 000100 nakon 2. shifta
    // 001000 nakon 3. shifta
    // 010000 nakon 4. shifta
    // 100000 nakon 5. shifta
    // 011111 nakon -1
    int free = (1 << n) - 1;

    // varijabla free označava koje stupce promatramo (1) odnosno ignoriramo (0)


    // ispisi rezultat rekurzije s memoizacijom
    cout << maxsuma(free,n) << endl;

    return 0;
}