6. Obchodnícke obtiaže vzorové riešenie

4
16 6 2 10
3 8 12 9

336

Najskôr sa pozrieme na jednoduchšie algoritmy, ktoré vás mohli pri riešení tejto úlohy napadnúť, následne si predstavíme dynamické programovanie a nakoniec v ňom nájdeme malý trik ku vzorovému riešeniu.

Jednoduché algoritmy

Prvá vec, ktorá nás napadne pri ľubovoľnej úlohe, je brute force. Ten však bude príliš pomalý. Navyše pri tejto úlohe je aj jeho implementácia netriviálna, takže je jednoduchšie sa zamyslieť nad rýchlejším riešením.

Ďalší jednoduchý prístup sú greedy algoritmy. No či už vyberáme pre zákazníka najlacnejšiu alebo najdrahšiu knihu, dá sa nájsť protipríklad, na ktorom nezvolíme optimálnu stratégiu. Poďme sa teda pozrieť na myšlienkovo náročnejšie riešenie, ktoré ale už bude korektné.

Dynamické programovanie

Táto úloha sa dá celkom príjemne riešiť pomocou dynamického programovania – dynamiky. Dynamika je algoritmus, v ktorom zo stavov, ktoré už poznáme, postupne počítame ďalšie, až kým sa nedostaneme ku výsledku.

V tejto úlohe bude naším stavom počet už predaných kníh a vrchné tri knihy na kope. Informácia, ktorú pre tento stav chceme vedieť, je maximum peňazí ktoré vieme mať vtedy zarobených. Medzi týmito stavmi sa presúvame predajom kníh. Pri každom predaji predáme jednu knihu (konkrétneho zákazníka vieme určiť z počtu predaných kníh) a namiesto nej do trojice známych kníh dáme ďalšiu knihu z kopy. Týmto nám vznikol nový stav. Ak už sme taký stav niekedy dosiahli, tak si porovnáme zarobené peniaze a zapamätáme si maximum.

Implementovať to budeme pomocou štvorrozmerného poľa, kde jedna súradnica bude počet predaných kníh, ďalšími tromi budú vrchné tri knihy na kope, a hodnota jedného políčka budú peniaze zarobené v danom stave.

Samotný algoritmus bude postupne prechádzať všetky políčka (stavy). Pre dané políčko si vypočíta stav, ktorý mu vznikne predajom prvej knihy, a na políčko tohto nového stavu skúsi uložiť peniaze, ktoré by takto zarobil. No čo ak sa na toto políčko už dostal predtým? Preto sa najskôr pozrie, či už na danom políčku nie je uložená väčšia hodnota, ako by zapisoval. Ak áno, tak nespraví nič, pretože by prepisoval optimálnejšie riešenie. V opačnom prípade zapíše novú hodnotu. To isté zopakuje pre druhú a tretiu knihu.

Keďže si pamätáme štvorrozmerné pole, kde každá zo súradníc môže mať veľkosť až \(n\), pamäťová zložitosť bude \(O(n^4)\). A keďže všetky tieto políčka počas výpočtu prechádzame, tak aj časová zložitosť bude \(O(n^4)\).

Už máme skoro vzorové riešenie, ale \(n^4\) je predsa len príliš pomalé a na najväčších vstupoch nestíha. Skúsme teda naše riešenie trochu zoptimalizovať.

Zlepšenie zložitosti

Pozrime sa bližšie na predaj jednej knihy. Zákazník príde, kúpi si jednu z vrchných troch kníh a odíde. Keďže sa jedna z vrchných troch kníh zobrala, štvrtá kniha z kopy sa “presunula” na tretie miesto. Toto sa deje pri každej kúpe knihy¹. Treťou knihou na kope bude teda po ľubovoľných \(k\) nákupoch vždy \(k+3\)-tia v pôvodnej kope.

Nám si teda stačí pamätať len túto tretiu knihu a celkový počet kníh si z nej budeme vedieť ľahko. Celkovo teda máme tri vnorené cykly, čo nám dáva časovú a aj pamäťovú zložitosť \(O(n^3)\).

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

#define MIN_INFTY -56789

int n, B[542], H[542];
int data[542][542][542];

int main(){

    cin >> n;   //načítame vstup
    for(int i = 0; i<n; ++i) cin >> H[i];
    for(int i = 0; i<n; ++i) cin >> B[i];
    
    H[n] = H[n+1] = H[n+2] = 0;
    B[n] = B[n+1] = H[n+2] = 0;
    //vytvoríme si sentinely, t.j. hranice na okraji našich hodnôt, aby sme
    //nemuseli ošetrovať hraničné prípady. V tomto prípade doplníme hodnoty o
    //tri bezcenné knihy na spodku kopy a troch švorc kupcov na konci. Je
    //ľahké vidieť, že v každom optimálnom riešení si títo traja kupci vezmú
    //tieto tri knihy, a nám to ušetrí kopu if-ov

    for(int i = 0; i<2; ++i) {  //inicializujeme si pole
        for(int j = 0; j<n+2; ++j) {
            for(int k = 0; k<(n+2); ++k) {
                data[i][j][k] = MIN_INFTY;
            }
        }
    }
    
    data[0][1][2] = 0; //počiatočný stav
    
    for(int i=0; i<n+1; i++){   //prejdeme cez jednotlivé stavy
        for(int j=i+1; j<n+2; j++){
            for(int k=j+1; k<n+3; k++){
                int current = data[i][j][k];
                data[j][k][k+1] = max(data[j][k][k+1], current + H[i]*B[k-2]);
                data[i][k][k+1] = max(data[i][k][k+1], current + H[j]*B[k-2]);
                data[i][j][k+1] = max(data[i][j][k+1], current + H[k]*B[k-2]);
            }
        }
    }

    cout<<data[n][n+1][n+2]<<endl;  //vypíšeme stav, kde nám ostávajú nami
                                    //doplnené bezcenné knihy
}

Vzorové riešenie

Pamäťová zložitosť \(O(n^3)\) však stále nestačí na plný počet bodov, skúsme ju teda trochu orezať.

Pri predchádzajúcej optimalizácií sme využili fakt, že tretia kniha na kope sa nám pri každom predaji zmení na tú pod ňou. Tento fakt nám ale dáva viac, než sme využili. Vďaka tomu totiž vieme, že zo stavov, kde tretia kniha je \(k\)-ta sa vieme dostať jedným predajom len do stavov, kde tretia kniha je \(k+1\)-vá. A naopak, do stavov kde tretia kniha je \(k\)-ta sa vieme dostať len zo stavov, kde tretia kniha je \(k-1\)-vá. Keďže potrebujeme len stavy \(k-1\), nemusíme si pamätať všetky predchádzajúce. Stačí nám, keď si v jednom riadku poľa budeme pamätať už vypočítané stavy a do druhého budeme zapisovať novovypočítané stavy. No a keď ich dorátame, tak nám stačí len vymeniť riadky a počítať ďalej.

Tým, že si v jednom momente pamätáme stavy len pre dva prípady tretej knihy na kope, sme práve odobrali ďalšie \(n\) z pamäťovej zložitosti. Pamäťová zložitosť teda bude \(O(n^2)\).

#include<iostream>
#include<algorithm>
#include<vector>


using namespace std;

#define MIN_INFTY -1023456789

int n, B[542], H[542];
int data[2][542][542];  
//Prvá súradnica nám bude reprezantovať tretiu knihu v kope.


int main(){
    cin >> n;
    for(int i = 0; i<n; ++i) cin >> H[i];
    for(int i = 0; i<n; ++i) cin >> B[i];
    
    for(int i = 0; i<2; ++i) {
        for(int j = 0; j<n+2; ++j) {
            for(int k = 0; k<n+2; ++k) {
                data[i][j][k] = MIN_INFTY;
            }
        }
    }
    
    data[0][0][1] = 0; //Inicializujeme si počiatočný stav

    for(int i = 0; i<n; ++i) {
        for(int j = 0; j<n+2; ++j) {
            for(int k = 0; k<n+2; ++k) {
                int current = data[i%2][j][k];
                data[(i+1)%2][j][k]   = max(data[(i+1)%2][j][k], current+B[i]*H[i+2]);
                data[(i+1)%2][i+2][k] = max(data[(i+1)%2][i+2][k], current+B[i]*H[j]);
                data[(i+1)%2][j][i+2] = max(data[(i+1)%2][j][i+2], current+B[i]*H[k]);
                //simulujeme predaj postupne tretej, prvej a druhej knihy v kope
            }
        }
    }
    cout << max(data[n%2][n][n+1], data[n%2][n+1][n]) << endl;
}