Množiny

Množina je ďalší matematický objekt, ktorý nám vie pomôcť. Zoberme si ďalšiu úlohu v tejto lekcii - zlodej. V tejto úlohe ste zlodej, ktorý sa snaží z domu ukradnúť predmety s čo najväčšou spoločnou váhou, má však batoh, ktorý unesie najviac hmotnosť $w$. Chcete teda vybrať takú sadu vecí, že ich spoločná váha je čo najbližšie k $w$.

Táto úloha je od predchádzajúcej trochu odlišná. Je pravda, že by sme sa stále mohli pýtať na všetky permutácie prvkov, pridávať ich v tom poradí do batohu a keď batoh naplníme, prestaneme a zrátame, koľko vážia dokopy veci v batohu.

To však ani zďaleka nie je to, čo by sme chceli robiť, dokonca to od nás nevyžaduje ani úloha. Nás totiž vôbec nezaujíma, v akom poradí vložíme veci do batoha. Nás zaujíma, ktoré veci budú na konci v batohu. Predstavte si, že viete vložiť $k$ vecí do batohu. Existuje $k!$ možností ako ich tam vložiť, ale stále dostaneme to isté -- tieto predmety sa do batohu zmestia a zaberú stále rovnako miesta. Bolo by fajn teda vyskúšať túto množinu len raz.

A tu prichádzame na koreň problému -- množiny. Chceli by sme vedieť rýchlo prezerať všetky množiny vecí (množina je reprezentovaná tým, či danú vec zoberiem alebo nie) a potom overiť, či daná množina vyhovuje. Výhodou je, že všetkých množín z $n$ prvkov je $2^n$, čo je stále veľké číslo, ale oproti $n!$ nám to umožňuje spracovať všetky množiny až z $25$ prvkov. Opäť existuje niekoľko prístupov na riešenie tohoto problému.

Prvým je znova rekurzia. V tomto prípade opäť budeme mať množinu vecí, ktoré ešte chceme zadeliť a množinu vecí, ktoré už patria do našej množiny. Na začiatku volania zoberieme prvú vec, ktorá je voľná a rozhodneme sa, či ju zobrať alebo nie. Samozrejme, keďže sa snažíme nájsť všetky možnosti, treba skúsiť obe rozhodnutia. Keď prvok vyberieme, zaradíme ho do množiny vecí, ktoré už máme, vyhodíme ju z nerozhodnutých a rekurzívne sa zavoláme. Ak si ju neberieme, aj tak ju vyhodíme z nerozhodnutých vecí, lebo sme sa už rozhodli, že ju neberieme a zavoláme sa rekurzívne. Dostaneme takýto jednoduchý kúsok kódu:

//rekurzívna funkcia na generovanie množín
void mnoziny(vector<int> na_spracovanie, vector<int> mnozina) {
    if(na_spracovanie.size()) {
        //už som spracoval všetky prvky, v mnozina je ďašia množina, spracujem ju
        return ;
    }
    int x=na_spracovanie[0];
    //nove_na_spracovanie obsahuje všetky okrem prvého prvku, ktorý akurát spracujeme
    vector<int> nove_na_spracovanie;
    for(int i=1; i<na_spracovanie.size(); i++)
        nove_na_spracovanie.push_back(na_spracovanie[i]);
    //prvý prvok nezoberiem
    mnoziny(nove_na_spracovanie, mnozina);
    //vyberiem prvý prvok
    mnozina.push_back(x);
    mnoziny(nove_na_spracovanie, mnozina);
}

Opäť to však nie je najľahší prístup. Existuje aj prístup oveľa jednoduchší, samozrejme, ale viac trikovejší. Majme našich $n$ vecí a dajme im nejaké poradie, napríklad podľa toho, kedy sa vyskytli na vstupe, nultý, prvý až $n-1$-vý. Každú množinu si teraz viem predstaviť ako reťazec dlhý $n$ znakov, tvorených zo znakov $0$ a $1$. $1$ znamená, že prvok sa v tejto množine nachádza, $0$ je opak. Dobre, ale toto je vlastne spôsob, akým sa zapisujú binárne čísla. Stačí $i$-temu prvku v poradí pŕiradiť hodnotu $2^i$ a z našeho reťazca sa razom stane celé číslo. A presne toto bude princíp našho riešenie.

Môžeme si uvedomiť, že čísla od $0$ po $2^n-1$ nám postupne v dvojkovej sústave kóduju všetky možné množiny $n$ prvkov, začínajúc prázdnou a končiac takou, čo obsahuje všetky prvky. A s číslami sa v C++ pracuje veľmi pohodlne a keďže sú interne reprezentované ako $0$ a $1$, tak s nimi vieme robiť veľa pekných operácií. Tu je program, ktorý ukazuje, ako sa dá postupne prejsť cez všetky množiny a tiež zistiť, ktoré čísla do nich patria:

//prvky, z ktorých idem robiť množiny
vector<int> prvky;
for(int i=0; i<(1<<prvky.size()); i++) {
    //spracujem ďalšiu množinu reprezentovanú číslom i
    for(int j=0; j<prvky.size(); j++) {
        if(i&(1<<j)) {
            //množina i obsahuje j-ty prvok
        }
        else {
            //množina i neobsahuje j-ty prvok
        }
    }
}

S niektorými operáciami ste sa možno ešte nestretli. 1<<n je takzvaný bitový posun doľava. V princípe to znamená, že k číslu naľavo ($1$) v bitovom zápise pridá číslo napravo ($n$) núl. Teda z pôvodného čísla vznikne číslo $2^n$. Ďalšia neznáma je i&(1<<j). Už vieme, že sa vlastne pýtame na to, že $i&2^j$. Čo to ale je? Znak & predstavuje bitový and, ktorý zoberie bitový zápis čísla $i$, bitový zápis čísla $2^j$ a bit po bite vykoná and. Ako vieme, $1 and 1 = 1$ a $0 and hocičo = 0$. Číslo $2^j$ obsahuje jedinú jednotku na $j$-tom mieste, všade inde sú $0$. To znamená, že tento výraz bude mať hodnotu $0$, ak sa na $j$-tom mieste v množine $i$ nachádza $0$ a hodnotu $2^j$, ak sa tam nachádza $1$. A keďže v C++ $0$ je false a všetko ostatné je true, podmienka bude splnená práve vtedy, keď množina $i$ obsahuje $j$-ty prvok. Šikovné, nie?

Ďalej